问:
What is the proper way to combine relative error when multiplying/dividing?
I need to multiply two independently-gathered single-variable data points with percent errors. Looking online, I have found two contradictory ways to combine the percent errors. One way is to simply sum them together; the other is to take the square root of the sum of the squares. At least in physics, I've always used the first way, but I have found several websites online supporting either position. Which one is the correct way? If they are both correct, what situations do I use each method in?

Site supporting the first method:
1
Sites supporting the second method:
2
3

I noticed that in the second site, they said that all of their formulas were premised on the two data points being independent. That makes me feel more that the second method is correct for my case, but I'm not totally sure.

答:
Neither of these is correct, although they are both approximately correct if the errors are small. The exact answer is the following. If you're multiplying a quantity which you are uncertain about by a factor of $1 \pm p$ with a quantity which you are uncertain about by a factor of $1 \pm q$, then you are uncertain about their product by a factor of

$$(1 \pm p)(1 \pm q) = 1 \pm p \pm q + pq.$$

This is simple arithmetic. For example, if you have 10% uncertainty about the first quantity and 8% uncertainty about the second quantity, then you're uncertain about their product by a factor of

$$(1 \pm 0.1)(1 \pm 0.08) = 1 \pm 0.18 + 0.008.$$

Note that this is not symmetric about $1$; the upper bound is $1.1 \times 1.08 = 1.188$ and the lower bound is $0.9 \times 0.92 = 0.828$. You can say conservatively that the uncertainty in the product is $1 \pm 0.188$, or 18.8%, but this loses a little bit on the lower end.

If $p$ and $q$ are small then $pq$ is very small and $\pm p \pm q + pq$ is approximately $\pm p \pm q$, which is where "add the relative errors" comes from, but it's worth knowing that this is an approximation that breaks down if $p$ and $q$ are not small (or if you are multiplying many terms).

If you read the second link more carefully it tells you to compute the square-root-of-sum-of-squares for the absolute error of a sum (at least I think that's what it's doing; it's not very clear since the term "SE" hasn't been defined at all); this isn't a method being suggested for the relative error of a product at all. The main reason you'd compute the error this way is if you have reason to believe that your errors are well-modeled by independent normal / Gaussian distributions. This square-root-of-sum-of-squares behavior governs how independent Gaussians add: we have

$$N(0, \sigma_1) + N(0, \sigma_2) \sim N(0, \sqrt{\sigma_1^2 + \sigma_2^2}).$$

But this is a specific modeling assumption that may break down. The exact expression I give above gives worst-case bounds which are independent of the nature of the error as long as you actually know a bound on it.


问:
Show that there is exactly one element in $A$ congruent to $1$ modulo $p$ as follows.
Let $p$ be a prime. Let $A = \{a,2a,3a,\ldots,(p-1)a \}$, where $\gcd(a,p)=1$. Show that there is exactly one element in $A$ congruent to $1$ modulo $p$.

My attempt:
It is suffices to show that for each $a \in \{1,2,3,\ldots,p-1\}$, there is exist exactly one $b \in \{1,2,3,\ldots,p-1\}$ such that $ab \equiv 1 \pmod{p}$.
Suppose there is exist an element in $A$, say $c$, such that $ab \equiv ac \equiv 1 \pmod{p}$. Then,
\begin{equation*}
b \equiv 1\cdot b \equiv (ac)b \equiv (ab)c \equiv 1\cdot c \equiv c \pmod{p}
\end{equation*}
Hence, $b$ is unique and we're done.

Am i true? If not, how to show it?

答: By Fermat's little theorem $a^{(p-1)} \equiv 1 (mod \ p)$ if $\gcd(a,p)=1$ therefore $a a^{(p-2)} \equiv 1 (mod \ p)$ thus by selecting the smallest positive integer congruent to $a^{(p-2)} (mod \ p)$ you have the solution.

ContentLicense: CC BY-SA 4.0


问:
Is $\frac{o(x)}{x^2}=o\left(\frac{1}{x}\right)$ for $x\to0$?
While solving a limit as $x\to 0$, I had a doubt: is it true that for $x\to0$ it is $o(x)\cdot\frac{1}{x^2}=o\left(\frac{1}{x}\right)$?

In my opinion yes, because of this: $f(x)=o(g(x))$ for $x\to0$ if
$$\lim_{x\to0} \frac{f(x)}{g(x)}=0$$
So if I use this definition with $o(x)\cdot\frac{1}{x}$ in place of $f(x)$ and $\frac{1}{x}$ in place of $g(x)$, I get
$$\lim_{x \to 0} \frac{o(x)\cdot\frac{1}{x^2}}{\frac{1}{x}}$$
But it is
$$\lim_{x \to 0} \frac{o(x)\cdot\frac{1}{x^2}}{\frac{1}{x}}=\lim_{x \to 0} \frac{o(x)}{x}=0\implies\lim_{x \to 0} \frac{o(x)\cdot\frac{1}{x^2}}{\frac{1}{x}}=0$$
Where $\frac{o(x)}{x} \to 0$ as $x\to0$ because of little-o definition. This shows that for $x\to0$ it is s $o(x)\cdot\frac{1}{x^2}=o\left(\frac{1}{x}\right)$.

Is this correct? I'm not sure if I can use functions that contain themselves little o-notation in the definition of little-o, I mean that I'm not sure if it is correct to use $o(x)\cdot\frac{1}{x^2}$ as $f$. I think that it can be done because $o(x)$ is a function of $x$ itself, so it is reasonable to use $o(x)\cdot\frac{1}{x^2}$ as $f$, can someone confirm me this or tell me if it is wrong?

答:
An easy way to think about little $o$'s is to realize that $o(f(x))$ can be written as $o(f(x))=f(x)  \varepsilon(x)$ where $\lim \varepsilon(x)=0$ as $x\rightarrow 0$. This is a direct consequence of the definition of $o(x)$.

With that, $$\frac {o(x)}{x^2}=\frac{x\varepsilon(x)}{x^2}=\frac{\varepsilon(x)}{x}=o\left(\frac 1 x\right)$$


问:
Aproximating rational with fraction with "smallest numerator and denumerator possible"
For example $0.795=\frac{159}{200}$. But is there a way to find fraction with smaller numerator and denumerator that will represent number $0.795xyz...$ i.e. it will approximate our given number?

I need algorithm or some procedure for this.

答:
The smallest denominator $q$ is $q=44$ corresponding to $$\frac pq=\frac{35}{44}=0.795\overline{45}$$
To see this, note that
$$ \frac ab=\frac{31}{39}=0.79487\ldots$$
is too small and
$$\frac cd=\frac{4}{5}=0.8$$
is too big.
For any fraction with $\frac ab<\frac pq<\frac cd$, we have
$$\frac pq-\frac ab=\frac{bp-aq}{bq}>0\qquad\frac cd-\frac pq=\frac{cq-dp}{dq}>0,$$
hence $$ bp-aq\ge 1\qquad cq-dp\ge 1$$
and finally (because $bc-ad=1$)
$$ q=(bc-ad)q=d(bp-aq)+b(cq-dp)\ge b+d=44.$$</p>

ContentLicense: CC BY-SA 3.0


问:
Can we multiply between two Derivative operator?
I don't know what should be the tile of my question sorry for that ..

I will explain here clearly ...

Suppose this is my integral :

$\int \frac{d^2x}{dt^2}dx$

I have to show that the integral is equal to $(\frac{dx}{dt})^2$

My steps :

$=\int \frac{d}{dt}(\frac{dx}{dt})dx$

$=\int d\frac{d^2x^2}{d^2t^2}$  Note:  Here I am multiplying  between the two operator like $dx \cdot dx=d^2x^2 $ and $dt \cdot dt=d^2t^2 $

$=(\frac{dx}{dt})^2$

So now my question is can we multiply like the way I did according to my note . If my procedure is wrong how can i show $(\frac{dx}{dt})^2$ from the integral

答:
I thought of another, even simpler way of solving this.

The derivative, $\frac{d}{dx}\left(\right)$, is actually a combination of two separate operations: the differential $d()$ and a division by $dx$.  Most of the time people combine these, but they are in fact separable.  Integration is actually the opposite of differentiation, not the derivative itself.  As an example, $d(x^2) = 2x\,dx$ and $\int 2x\,dx = x^2 + C$.

So, the second derivative is just the derivative of the derivative.  So,
$$y'' = \frac{d\left(\frac{dy}{dx}\right)}{dx}$$

So, the integral you are interested in is $\int y''\,dy$.  This can be expressed as:

$$ \int \frac{d\left(\frac{dy}{dx}\right)}{dx}\,dy $$

Rearranging slightly, we get:

$$ \int d\left(\frac{dy}{dx}\right) \frac{dy}{dx} $$

So, if we set $u = \frac{dy}{dx}$, this just becomes:

$$\int d(u)\, u \quad\text{or, written another way,}\quad \int u\,du$$

$\int u\,du$ is obviously $\frac{u^2}{2} + C$, and since $u = \frac{dy}{dx}$, then the solution is $$\frac{1}{2}\left(\frac{dy}{dx}\right)^2 + C$$


问:
Showing a function is not an inner product
From Axler's Linear Algebra Done Right, 6.A 1,

Show that the function that takes $((x_1,x_2),(y_1,y_2)) \in \mathbb{R}^2 \times\mathbb{R}^2$ to $|x_1 y_1|+|x_2 y_2|$ is not an inner product on $\mathbb{R}^2$.

My attempt:

I will verify all the properties of inner products:

Positivity

$|x_1 x_1|+|x_2 x_2|$ is always $\geq0$ so this holds.

Definiteness

$\langle (x_1,x_2),(x_1,x_2)\rangle=|x_1 x_1|+|x_2 x_2|=0$ only if $|x_1 x_1|=|x_2 x_2|=0$ so $(x_1,x_2)=0$

Additivity in first slot

$\langle (x_1,x_2)+(z_1,z_2),(x_1,x_2)\rangle =\langle (x_1+z_1,x_2+z_2),(x_1,x_2)\rangle=|(x_1+z_1) y_1|+|(x_2+z_2)y_2|=|x_1 y_1|+|z_1 y_1|+|x_2 y_2|+|z_2 y_2|=\langle (x_1,x_2),(y_1,y_2)\rangle +\langle (z_1,z_2),(y_1,y_2)\rangle$

Homogeneity in first slot

$\langle \lambda (x_1,x_2),(y_1,y_2)\rangle=\langle (\lambda x_1,\lambda x_2),(y_1,y_2)\rangle =|\lambda x_1 y_1|+|\lambda x_2 y_2|=\lambda|x_1 y_1|+\lambda|x_2 y_2|=\lambda(|x_1 y_1|+|x_2 y_2|)=\lambda\langle (x_1,x_2),(y_1,y_2)\rangle$

Conjugate symmetry

$\overline {\langle (y_1,y_2),(x_1,x_2)\rangle}=\overline {|y_1 x_1|+|y_2 x_2|}=\overline{|y_1 x_1|}+\overline{|y_2 x_2|}=|y_1 x_1|+|y_2 x_2|=|x_1 y_1|+|x_2 y_2|$

It seems to me that everything holds so I am not sure why this is not an inner product.

答: HINT. $|a+b|\neq |a|+|b|$, $|\lambda a|\neq \lambda |a|$. Consider negative numbers.


问:
Express "Someone has visited every country except Libya" using predicates and quantifiers.
I have expressed the statement "Someone has visited every country except Libya" using quantifiers as follows.

$$\exists x\forall y [V(x, y)\wedge \sim V(x, Libya))]$$
where $V(x, y)$ represents $x$ has visited country $y$.

Is the above representation correct?

Note: Domain for $x$ is all people in this world, and for $y$ is all countries.

答: No, it is not exactly correct, as pointed out by Michael in the comments. I'd write it as $$\exists x\forall y,\;\lnot V(x,y)\leftrightarrow y=Libya$$


问:
What qualities of an algebraic torus make it like a torus?
Why do we call it an algebraic torus?

What qualities of an algebraic torus make it like a torus?

D_S gives the following classical definition of an algeraic torus here Formal Definition of an Algebraic Torus:

"Clasical definition: Let $H \subseteq \operatorname{GL}_n(\overline{k})$ be a connected linear algebraic group over $k$.  So $H$ is a Zariski closed subgroup of $\operatorname{GL}_n(\overline{k})$ which is irreducible, and the polynomials of the radical ideal $I(H)$ corresponding to $H$ can be chosen to have coefficients in $k$, rather than just $\overline{k}$.   We say that $H$ is an algebraic torus if there exists a $g \in \operatorname{GL}_n(\overline{k})$ such that $gHg^{-1}$ consists of diagonal matrices."

答:
Over $\mathbb{C}$ the algebraic tori have the form $(\mathbb{C}^{\times})^n$, which has maximal compact subgroup an ordinary torus $T^n$. The inclusion of the maximal compact subgroup is a homotopy equivalence, and the two also have the same finite-dimensional representation theory (where for the algebraic torus we consider algebraic representations only). One can think of $(\mathbb{C}^{\times})^n$ as a complexification of $T^n$. The general case is by analogy with this one.

A major reason to work at this level of generality is to generalize the notion of a maximal torus from compact Lie groups to reductive algebraic groups. This can be done although I'm not the person to ask about how it works in detail.


问:
Two equivalent definitions of projective module $P$ (one involving right inverse), how do we make sense of these "replacements" in the proof?
I'm going through Rosenberg's Algebraic K-theory and its applications.  The following is a screenshot from the first few pages.

The definition of projective left $R$-module $P$ is: for any surjective hom $\alpha: M \twoheadrightarrow P$ there exists a right inverse $\beta : P \to M$ (i.e. such that $\alpha \circ \beta = \text{id}_P$).

The goal is to show that this is equivalent to the usual definition of projective module given in commutative diagrams at the top of the screenshot (i.e. that a commutative triangle can be completed for any surjection $\psi: M \twoheadrightarrow N$ and any hom $\varphi: P \to N$).

At the bottom of the screenshot it says we may replace $N$ by $\text{im}((\varphi, \text{id}_P))$ and $M$ by $\psi^{-1}(\text{im}(\varphi))$.  Firstly, do they mean replace the $N$ in $N \oplus P$ or the original $N$ (alone).  And, I don't understand how this will be the same problem as the original, so could you explain this section to me in detail?  Alternatively can you give a proof with more clarity?

答:
The final paragraph is less than clear, so it is no wonder you are a bit confused. Taken literally it might lead you astray (I will note where below). Also, this seems needlessly complicated to me, so I will indicate an alternative argument below after explaining what they are doing.

You are trying to prove that if every surjection onto $P$ has a right inverse, then the module $P$ is projective; that is, that whenever you have a surjection $M\to N$ and a map from $P$ to $N$, you can factor that map through $M$.

So, let $\psi\colon M\to N$ be a surjection, and let $\phi\colon P\to N$ be a map. We want to show that there exists a morphism $\theta\colon P\to M$ such that $\phi=\psi\circ\theta$.

To that end, we will construct a surjection onto $P$ whose right inverse will help us find $\theta$.

Let’s take the module $M\oplus P$, and map it to the module $N\oplus P$ by the map $(\psi,\mathrm{id}_P)$. This map takes $(m,p)$ and sends it to $(\psi(m),p)$. This is a surjection, since $\phi$ and $\mathrm{id}_P$ are surjections: given $n\in N$ and $p\in P$, there exists $m\in M$ such that $\psi(m)=n$, and then $(m,p)$ maps to $(n,p)$.

Let us also replace the morphism $P\to N$ with the morphism $P\to N\oplus P$ given by $(\phi,\mathrm{id}_P)$. This map takes $p\in P$ to $(\phi(p),p)$. Now we have a new diagram:
$$\begin{array}{ccl}
&&P\\
&&\downarrow(\phi,\mathrm{id}_P)\\
M\oplus P&\stackrel{(\psi,\mathrm{id}_P)}{\longrightarrow} & N\oplus P
\end{array}$$
Note that the vertical arrow is now one-to-one: for given $p\in P$, if $(\psi,\mathrm{id}_P)(p) = (0,0)$, then $p=0$.

Now we will replace this diagram yet again; it is here that they are less than clear. Taken literally, we would replace $N$ and $M$, but in fact we will replace $N\oplus P$ and $M\oplus P$:
instead of $N\oplus P$, let us put $\mathrm{Im}(\psi,\mathrm{id}_P)= N’$ (for ease; but note that this is a submodule of $N\oplus P$); and instead of $M\oplus P$, we will put $(\psi,\mathrm{id}_P)^{-1}(N’)$.
$$\begin{array}{ccl}
&&P\\
&&\downarrow(\phi,\mathrm{id}_P)\\
(\psi,\mathrm{id}_P)^{-1}(N’)&\stackrel{(\psi,\mathrm{id}_P)}{\longrightarrow} &N’
\end{array}$$
Note that the bottom arrow is still surjective, and the vertical arrow is still injective (the latter is just a restriction of the previous vertical arrow). But now the vertical arrow is an isomorphism: it is surjective by construction. So the vertical arrow is now an isomorphism.

So now we have a surjection
$$(\psi,\mathrm{id}_P)^{-1}(N’)\stackrel{(\psi,\mathrm{id}_P)}{\longrightarrow} N’\stackrel{(\phi,\mathrm{id}_P)^{-1}}{\longrightarrow} P.$$
We can take the inverse at the end because the restriction of $(\phi,\mathrm{id}_P)$ was an isomorphism.

This composition is a surjection, so it has a right inverse $\beta\colon P\to (\psi,\mathrm{id}_P)^{-1}(N’)\leq M\oplus P$. We claim that if you take this $\beta$ we will get the extension we want to start with (that is, the map $P\to M$ we are looking for); well, not quite this extension, but rather $\pi_M\circ\beta\colon P\to M$.

To verify this, take $p\in P$. The $\beta(p)$ has the property that $(\phi,\mathrm{id}_P)\circ(\psi,\mathrm{id}_P)^{-1}(\beta(p))=p$. So $\beta(p)=(m,q)$ for some $m\in M$ and $q\in P$. Then $(\phi(m),q)$ must be equal to $(\psi(p),p)$. Thus, $q=p$, and $\psi(p) = \phi(m)=\phi(\pi_M(\beta(p)))$.

Thus, $\pi_M\circ\beta\colon P\to M$ has the property that $\phi(\pi_M\circ\beta(p))=\psi(p)$, hence this is the morphism we are looking for.

Now, I think the instructions to replace and replace again are a little too complicated (as may be apparent above). We can do all of the above without so much be using a free module as an auxiliary. This uses a third equivalent condition to being free:

Theorem. Suppose that $P$ is a module such that every surjection $M\to P$ has a right inverse. Then there exists a module $Q$ such that $Q\oplus P$ is free.

Proof. Let $F$ be a free module that surjects onto $P$ (this is always possible; e.g., you can take the free module on the underlying set of $P$), $\pi\colon F\to P$. Then this surjection has a right inverse $\beta\colon P\to F$. Since $\pi\beta=\mathrm{id}_P$, then $\beta$ is injective. Now let $Q=\mathrm{ker}(\pi)$. If $x\in Q\cap \beta(P)$, then $x=\beta(p)$, so $0=\pi(x)=\pi(\beta(p))=p$. Thus, $Q\cap\beta(P)=\{0\}$. Now let $x\in F$. then $x-\beta(\pi(x))\in Q$, $\beta(\pi(x))\in \beta(P)$, so $x=\beta(\pi(x))+ (x-\beta(\pi(x)) \in \beta(P)+Q$. Thus, $F=\beta(P)\oplus Q\cong P\oplus Q$, as desired. $\Box$

Note: In fact, this is also equivalent to being projective, and the equivalence theorem that I am familiar with usually places all three conditions, not just the two you are dealing with.

So: assume that every surjection onto $P$ has a right inverse. In particular,  there exists a $Q$ such that $P\oplus Q$ is free.

Now assume we have a surjection $\psi\colon M\to N$ and a morphism $\phi\colon P\to N$. Let $Q$ be such that $Q\oplus P$ is free, $F$, and let $f\colon F\to N$ be given by $f(x) = \phi(\pi_P(x))$, where $\pi_P\colon Q\oplus P\to P$ is the projection onto the second coordinate. Let $B$ be a basis for $F$.

For each $b\in B$, $f(b)\in N$, hence there exists $m\in M$ such that $\psi(m)=f(b)=\phi(\pi_P(x))$. Define a map $\Theta\colon B\to M$ by $\Theta(b)=m$ for any one such choice of $m$. Since $F$ is free, this defines a (unique) morphism $\Theta\colon F\to M$. Now let $\theta\colon P\to M$ be given by $\theta(p) = \Theta(0,p)$. Then $\psi(\theta(p)) =\phi(\pi_P(0,p)) = \phi(p)$. Hence $\psi\circ\theta = \phi$, which is what we need.


问:
"Taylor Series" analog for functionals?
For a function $f(x)$, it is possible to write it as a taylor series centered around a point $x=a$:

$$f(x)=\sum_{n=0}^{\infty}\frac{f^{(n)}(a){(x-a)}^{n}}{n!}=f(a)+f'(a)(x-a)+\frac{f''(a)(x-a)^{2}}{2}+...$$

(Of course, there's a lot more mathematical nuance to Taylor Series expansion, I just want to lay it out loosely here as a basis for my intuition.)

I'm wondering if there's anyway to apply this to functionals, that is, a functional $F[f(x)]$ that maps the function $f(x)$ to an output. Is there a way to "rewrite" a functional as a series such as this:

$$F[f(x)]=a_0+a_1(f(x)-\phi(x))+a_2(f(x)-\phi(x))^2+...$$

Where $\phi(x)$ is a function that acts analogously to the point $x=a$  in a Taylor expansion.

(Again, I'm using all of my terminology and notation pretty loosely here. I'm not going for robust mathematical rigoorousness; I just want to express my intuition behind this idea.)

Is this "Functional expanded as a series" idea a thing? What is it called? Does it have any applications?

答:
It seems counter intuitive, but if you forget functionals (That is functions from functions to numbers) and just look at functions from functions to functions) you can build a taylor series like idea somewhat intuitively. I'm still working out the details of it, but i have been able to use it to show for example

$$ f(x+1) = f + f' + \frac{1}{2!}f''+\frac{1}{3!}f''' + ... $$

See here: How to build taylor series for infinite dimensional objects? for how to construct such series and for a list of problems that I encounter.

Somehow, most ideas in calculus generalize very cleanly in the context of "functions of functions" but fail to generalize EASILY (not saying they dont at all) in the context of functionals.

Title: "Taylor Series" analog for functionals?


答:
There are some brute force approach is involved in my solution. Given that this is an Olympiad question, there should be a way to avoid the brute force approach. The main idea of the solution comes from the comment https://artofproblemsolving.com/community/c6h2389832p19615716 by Rickyminer and a solution to a similar problem https://artofproblemsolving.com/community/c6h347925p1865700 by Pathological in AOPS.

Case 1: $\gcd(n,2021)=1$

We proceed as Minh Hien did. Since $\gcd(n,n+2021)=1$, the equation
$$
n(n+1- \phi(n)) = (n+2021)(n+2022 - \phi(n+2021)) \ \ (1)
$$
gives $n+2021 | n+1-\phi(n)$. This is a contradiction.

Case 2: $\gcd(n,2021)=43$

We write $n=43k$. We have $\gcd(k,47)=1$, the equation (1) becomes
$$
k(43k+1-\phi(43k))=(k+47)(43k+2022-\phi(43(k+47)).
$$
Since $\gcd(k,k+47)=1$, there is a positive integer $t<43$ such that
$$
43k+1-\phi(43k)=t(k+47),
$$
$$
43k+2022-\phi(43(k+47))=tk.
$$
By subtracting the second from the first, we have
$$
\phi(43(k+47))-\phi(43k)=47(t+43).
$$
Since $42$ divides the LHS, we have $t=41$. This gives
$$
\phi(43k)=2k-1926
$$
$$
\phi(43(k+47))=2k+2022.
$$
Let $k+47=43^e(k+47)_{43}$ where $\gcd((k+47)_{43},43)=1$. Let $k=43^fk_{43}$ where $\gcd(k_{43},43)=1$.
We obtain
$$
43^{e-1}\phi((k+47)_{43})-43^{f-1}\phi(k_{43})=47\cdot 2.  \ \ (2)
$$
One of the two terms on the LHS must be $2$ mod $4$. If the first term is $2$ mod $4$, then $(k+47)_{43}$ is $p^a$, $2p^a$, or $4$ for odd prime $p$.
For these numbers $\phi((k+47)_{43})/(k+47)_{43}$ is usually large. To be precise, we have the inequality
$$
\frac{\phi(43(k+47))}{43(k+47)} = \frac{2k+2022}{43(k+47)} \geq \left(1-\frac1{43}\right) \cdot \frac13.
$$
The inequality gives $k\leq 113$. We leave this to brute force check.

If the second term of (2) is $2$ mod $4$,
$$
\frac{\phi(43k)}{43k}=\frac{2k-1926}{43k} \geq \left(1-\frac1{43}\right)\frac13
$$
does not have a solution.

Case 3: $\gcd(n,2021)=47$

We proceed similarly as in Case 2. The equation (1) becomes
$$
k(47k+1-\phi(47k))=(k+43)(47k+2022-\phi(47(k+43)).
$$
Write $n=47k$, $gcd(k,43)=1$. We obtain
$$
\phi(47k)=2k-1934,
$$
$$
\phi(47(k+43))=2k+2022,
$$
and
$$
47^{e-1}\phi((k+43)_{47})-47^{f-1}\phi(k_{47})=43\cdot 2. \ \ (3)
$$
If the first term is $2$ mod $4$, then $(k+43)_{47}$ is $p^a$, $2p^a$, or $4$ for odd prime $p$. Then we have
$$
\frac{\phi(47(k+43))}{47(k+43)}=\frac{2k+2022}{47(k+43)} \geq \left(1-\frac1{47}\right)\cdot \frac13.
$$
The last inequality gives $k\leq 102$. We leave this to a brute force check.

If the second term of (3) is $2$ mod $4$, then we have no solution similarly as in Case 2.

Case 4: $\gcd(n,2021)=2021$

We write $n=2021k$.
The equation (1) becomes
$$
k(2021k+1-\phi(2021k))=(k+1)(2021k+2022-\phi(2021(k+1)).
$$
Proceeding as in Case 2, we have
$$
\phi(2021k)=178k-1842,
$$
$$
\phi(2021(k+1))=178k+2022,
$$
and
$$
43^{e_1-1}47^{e_2-1}\phi((k+1)_{43,47}) - 43^{f_1-1}47^{f_2-1}\phi(k_{43,47})=2. \ \ (4)
$$
If the first term is $2$ mod $4$, we have $(k+1)_{43,47}$ is $p^a$, $2p^a$, or $4$ for odd prime $p$. Then
$$
\frac{\phi(2021(k+1))}{2021(k+1)}=\frac{178k+2022}{2021(k+1)} \geq \left(1-\frac1{43}\right)\left(1-\frac1{47}\right)\frac13.
$$
The last equality gives $k\leq 2$. But, this does not satisfy the equality above.

Brute force cases

The cases with brute force checking left are covered with a Python code that there are no solutions.

Body:
VMO 2021:

Find all integers $n \geq 2$ such that: $n(n+1- \phi(n)) = (n+2021)(n+2022 - \phi(n+2021))$

I think $n$ does not exsist.

+, If $\gcd(n,2021)=1 \Rightarrow \gcd(n+2021,n)=1$

then $(n+2021) \mid (n+1- \phi(n))$

What should I do next?


问:
Pell's d prime (often) implies that x(d-1) is prime?
I have found a few patterns in my study of Pell’s equation x(d)^2-dy(d)^2=1.
One is this: If d is a prime then x(d-1) is also prime.

It doesn’t hold for all primes, but it is a pattern which holds for 17 of the 21 first (relevant) primes from 2 to 100. (There are more primes below 100 but several values are irrelevant since x(d-1) does not exist d=2, 5, 17 and 37).

I know that in many cases you will find a pattern which is just from statistics with just a few numbers.  I believe the phenomenon even has its own law, “the law of small numbers”   (among which “anything can happen”).

My inability to use mathematical software makes it impractical to improve my statistics. Does anybody know if this pattern prevails for a collection of the equations with higher numbers of d, or if there might be a reason for such a pattern?

答:
As I understand it by $x(d)$ you mean the $x$ for the smallest solution in positive integers.

Since $x(d-1)$ satisfies $x^2-(d-1)y^2=1$ it cannot have any common factor with $d-1$ or with $y$. For odd primes $d$ this rules out 2 and at least one other prime $<d$ as possible factors for $x$, which should make the occurence of prime $x(d-1)$ very slightly less surprising.

Checking the occurence for the first $N$ primes I got this table, which illustrates that the cases where $x(d-1)$ are prime are a minority for $N$ larger than 150, and look to be a diminishing proportion as $N$ grows.

$$
\begin{array}{c|c|c|c}
N & \mathrm{Relevant} & x(d-1)~\mathrm{is~prime} & \mathrm{fraction} \\
\hline\\
25 & 21 & 17 & 81\% \\
100 & 92 & 54 & 59\% \\
150 & 69 & 150 & 49\% \\
1000 & 983 & 252 & 26\% \\
10000 & 9949 & 1220 & 12\% \\
20000 & 19932 & 1987 & 10\% \\
\end{array}
$$


问:
Ring of global sections of a large twist of a vector bundle is not zero
This is Vakil 18.5 D (the first claim), self-study. Please note this is an intermediate step in the classification of vector bundles on $\mathbb P^1_k$, so we may not use that result.

We have to show that if $\mathcal E$ is a rank $r$ locally free sheaf on $\mathbb P^1_k$, then for $m <<0$,

$$\operatorname{Hom}(\mathcal O(m), \mathcal E) \neq 0$$

To begin, we note that the sheaf Hom $\operatorname{\mathcal Hom}(\mathcal O(m), \mathcal E) \simeq \mathcal E(-m)$ by a previous exercise. Hence we need to show

$$\Gamma (\mathbb P^1_k, \mathcal E(-m)) \neq 0$$

for $m << 0$. Vakil then says to use Serre vanishing, which gives us that

$$H^i (\mathbb P^1_k, \mathcal E(-m)) = 0$$

for $m <<0$ and $i > 0$, but I do not see why this forces $H^0$ to be nonzero.

答:
Attempt at a solution:

We wish to show $\Gamma (\mathbb P^1_k, \mathcal E(-m)) \neq 0$ for $m <<0$.

Filter $\mathcal E$ as

$$0 = \mathcal E_0 \subset \mathcal E_1 \subset ... \subset \mathcal E_r = \mathcal E$$

such that each subquotient is some invertible sheaf $\mathcal L_i \simeq \mathcal O(n_i)$ on $\mathbb P^1_k$ using Stacks OAYP (which does not use the classification of vector bundles on $\mathbb P^1_k$, and I have been through its proof before for previous exercises.)

This admits an exact sequence

$$0 \to \mathcal E_{r - 1} \to \mathcal E \to \mathcal O(n_r) \to 0$$

By Serre Vanishing, if $m<<0$, $H^i(\mathbb P^1_k, \mathcal E(-m)) = 0$ for all $i > 0$.

Tensor the above exact sequence by $\mathcal O(-m)$ for $m << 0$ that the above holds; another condition will be added to the size of $m$ momentarily. This preserves exactness, and gives

$$0 \to \mathcal E_{r - 1}(-m) \to \mathcal E(-m) \to \mathcal O(n_r - m) \to 0$$

By the Serre vanishing observation above, taking global sections is an exact functor, giving

$$0 \to \Gamma (\mathbb P^1_k, \mathcal E_{r - 1}(-m)) \to \Gamma(\mathbb P^1_k,\mathcal E(-m)) \to \Gamma(\mathbb P^1_k,\mathcal O(n_r - m) ) \to 0$$

But we already know by Cohomology of $\mathbb P^n_A$ that $\Gamma(\mathbb P^1_k,\mathcal O(n_r - m) ) \neq 0$ for $m << 0$, so impose that additional condition on the size of $m$ before you twist above, and you will have

$$\Gamma(\mathbb P^1_k,\mathcal E(-m)) \neq 0$$


问:
Prove $|f(x)-p_{3}(x)| \leq \frac{1}{384} \max\limits_{0 \leq x \leq 1}|f^{(4)}(x)|$
Given $f(x)\in C^4[0,1]$, and a polynomial $p_3(x)$ of degree $3$ s.t. $p_3(0)=0,p_3'(0)=f'(0),p_3(1)=f(1),p_3'(1)=f'(1)$. Prove that, $\left|f(x)-p_{3}(x)\right| \leq \dfrac{1}{384} \max\limits_{0 \leq x \leq 1}\left|f^{(4)}(x)\right|$.

I thought it may relate to Simpson's rule, but it seems to be not the case. Also I thought it may relate to Orthogonal Projection on a Polynomial Space, but I don't know how to proceed either.

Can anyone help? And, are there any further suggestions on these kind of problems(i.e. given a function, and a polynomial whose values and derivates are related to the function, then estimate)?

Body:
First define
$$
 g(x) = f(x) - p_3(x) \\
 q(x) = x^2(1-x)^2
$$
and note that $g(0) = g'(0) = g(1) = g'(1) = 0$ and $g^{(4)} = f^{(4)}$.

$q \not \equiv 0$  is chosen as a polynomial satisfying $q(0) = q'(0) = q(1) = q'(1) = 0$ of smallest possible degree.

Now let $0 < c < 1$ and define
$$
 h(x) = q(x) g(c)  - q(c) g(x) \, .
$$
Then
$$
 h(0) = h(c) = h(1) = 0 \\
 h'(0) = h'(1) = 0
$$
and repeated application of Rolle's theorem shows that $h^{(4)}(\xi) = 0$ for some $\xi \in (0, 1)$. So
$$
 0 = h^{(4)}(\xi) = q^{(4)}(\xi) g(c)  - q(c) g^{(4)}(\xi) \\
= 24 (f(c)-p_3(c)) - c^2(1-c)^2 f^{(4)}(\xi)
$$
and therefore
$$
f(c)-p_3(c) = \frac{f^{(4)}(\xi)}{24} c^2(1-c)^2 \, .
$$
Finally, using $c(1-c) \le 1/4$, we conclude that
$$
|f(c)-p_3(c)| \le \frac{1}{24 \cdot 4 \cdot 4} \max_{0 \leq x \leq 1}|f^{(4)}(x)| \, .
$$


问:
How is a Generator Matrix for a (7, 4) Hamming code created?
I see that a generator matrix is created with the following formulae:

$$G = \left[I_{k}|P\right]$$

I do not understand what P is in this case. In my notes, I am told that in a (7, 4) Hamming code situation my
$$G =
\begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1   \end{pmatrix}$$

where P would be

$$P=\begin{pmatrix}  1 & 0 & 1 \\  1 & 1 & 1 \\  1 & 1 & 0 \\  0 & 1 & 1   \end{pmatrix}$$

How is this P generated?

答:
we named data as d1, d2, d3 ,d4

we named parity as p1, p2, p3

make a G matrix or generator matrix so it might look like this. hamming code (7,4)

\begin{matrix}\mathbf{1}&\mathbf{0}&\mathbf{0}&\mathbf{0}&\mathbf{1}&\mathbf{1}&\mathbf{0}\\\mathbf{0}&\mathbf{1}&\mathbf{0}&\mathbf{0}&\mathbf{1}&\mathbf{0}&\mathbf{1}\\\mathbf{0}&\mathbf{0}&\mathbf{1}&\mathbf{0}&\mathbf{0}&\mathbf{1}&\mathbf{1}\\\mathbf{0}&\mathbf{0}&\mathbf{0}&\mathbf{1}&\mathbf{1}&\mathbf{1}&\mathbf{1}\\\end{matrix}

the question is how to make the G matrix?

d1 =\begin{matrix}1\\0\\0\\0\\\end{matrix}d2=\begin{matrix}0\\1\\0\\0\\\end{matrix} d3 =\begin{matrix}0\\0\\1\\0\\\end{matrix}d4 =\begin{matrix}0\\0\\0\\1\\\end{matrix}

pay attention to bit 1, totally only 1 bit for each row and zero in all other rows. The position of d1, d2, d3, d4 will remain the same. but you may find some formula put parity before data. so it will not arrange from d1,d2,d3,d4,p1,p2,p3 but it will arrange from p1,p2,p3,d1,d2,d3,d4. or you may also find any variation p3 and p1 will interchangeable. p1 could be in the p3 position or vice versa.

5.
p1 =\begin{matrix}0\\1\\1\\1\\\end{matrix}
p2=\begin{matrix}1\\0\\1\\1\\\end{matrix}

p3=\begin{matrix}1\\1\\0\\1\\\end{matrix}

pay attention to bit 0, totally only 1 bit for each row and one in all other rows.
so don't be confused if sometimes you might find p4 or parity 4. it would be p4 =\begin{matrix}1\\1\\1\\0\\\end{matrix}

seems like both of 1 in data bit position or 0 in parity bit position is walking down the row.


答:
Let $x_0 \ne 0,1$, and
$$K = \frac{f(x_0) - p(x_0)}{x_0^2(x_0-1)^2}$$ Then the function
$$r(x) = f(x) - p(x) - K x^2(x-1)^2$$
satisfies
$$r(0) = r'(0) = 0\\
r(x_0) = 0\\
r(1) = r'(1) = 0$$
Hence $r$ has $5$ zeroes, counting multiplicities. Let's show that there exists $\xi \in (0,1)$ such that $r^{(4)}(\xi)=0$. This would be clear if the zeroes were distinct,but it also works here. Indeed, by Rolle, there exist $\alpha\in (0, x_0)$, $\beta\in (x_0, 1)$ such that $r'(\alpha) = r'(\beta) = 0$. Now we have $4$ distinct roots of $r'$ and we can finally get $\xi$ such that $r^{(4)}(\xi) =0$. But calculating we get
$$r^4(x) = f^{(4)}(x) - 24 K$$
and so $K= \frac{f^4(\xi)}{24}$. We therefore get
$f(x_0) - p(x_0) =\frac{f^{(4)}(\xi)}{24} x_0^2(x_0-1)^2$. Note that $\xi$ depends on $x_0$.
Note that a similar argument would work for any $x_0$, not necessarily in $(0,1)$. Therefore, we have the error term formula for Hermite interpolation
$$f(x) - p(x)= \frac{f^{(4)} (\xi_x)}{24}x^2 (x-1)^2$$
where $\xi_x$ lies between $x$ and $0$,$1$.

$\bf{Added:}$ The explicit form for the Lagrange interpolation polynomial and an alternate proof can be done using generalized Vandermonde determinant, for instance take a look at my answer here. You may obtain by passing to limit the remainder for Hermite interpolation. Or one can use confluent determinants, see for instance Turnbull- Theory of Equations. Notice the the quotient of determinants in the answer is the quotient of remainders for two functions. If the bottom function is $(x-x_1)\cdots(x-x_n)$ the estimate is for Lagrange interpolation. Now , the generalization is for quotients of remainders
$$\frac{f(x) -p_f(x)}{g(x) - p_g(x)} = \frac{f^{(n)}(\xi_x)}{g^{(n)}(\xi_x)}$$
for interpolation at $n$ points. Note that if the points coincide, we have the Taylor polynomial approximation.

Title: Prove $|f(x)-p_{3}(x)| \leq \frac{1}{384} \max\limits_{0 \leq x \leq 1}|f^{(4)}(x)|$

Body:
Given $f(x)\in C^4[0,1]$, and a polynomial $p_3(x)$ of degree $3$ s.t. $p_3(0)=0,p_3'(0)=f'(0),p_3(1)=f(1),p_3'(1)=f'(1)$. Prove that, $\left|f(x)-p_{3}(x)\right| \leq \dfrac{1}{384} \max\limits_{0 \leq x \leq 1}\left|f^{(4)}(x)\right|$.

I thought it may relate to Simpson's rule, but it seems to be not the case. Also I thought it may relate to Orthogonal Projection on a Polynomial Space, but I don't know how to proceed either.

Can anyone help? And, are there any further suggestions on these kind of problems(i.e. given a function, and a polynomial whose values and derivates are related to the function, then estimate)?


问:
Quick way to prove uniqueness of inverses in a vector space?
Is the following reasoning valid?

Theorem: The inverses in a vector space are unique.

Proof: Let $V$ be a vector space. Then $(V, +)$ is an abelian group, and since group inverses are unique, every vector $v \in V$ has a unique inverse $v^{-1} = -v$.

Of course, the direct way of proving it is straightforward, so I'm just wondering if this  "abstract nonsense" style of approach is just as rigorous. Thanks for any advice.

答:
For this to be “rigorous” you need to:

Prove that in an abelian group, inverses are unique (this is not an explicit part of the definition of abelian group, so it has to be established).

Prove that the underlying additive structure of a vector space makes its into an abelian group (this is not part of the usual explicit definition of a vector space, so it must be proven).

And in order to do 1, you have to do essentially what you do in a vector space without any reference to abelian groups: you first prove the identity is unique, then you prove inverses are unique.

So your proposal isn’t really “abstract nonsense”, and moreover requires you do to way more than what the direct proof asks to do, by requiring you to establish a more general proposition (something for all abelian groups/modules), and then by establishing that your object is also one of the more general class of objects.


问:
Finding a probability in a Poisson process which could stop.
Suppose someone catches fish according to a Poisson process with rate 2 fish per hour. He quits fishing for the day whenever an hour has gone by since his last catch, or after 8 hours, whichever comes first. For example, if he catches his first fish after exactly 14 minutes but then no other fish during the first 74 minutes, then he goes home after 74 minutes with one fish. What is the probability that he has caught exactly 3 fish after 2 hours?

Since in order to catch 3 fish, he must catch the first and second fish so that the first two interarrivals are less than 1. Assuming the first two interarrivals are truncated exponentials with rate 2 that range from 0 to 1, I found the PDF of the sum of the two, which happens to be a piecewise function. The integrands in the two WolframAlpha links are the PDFs from 0 to 1 and then 1 to 2, and we see the integral is 1 for the sum of both parts.

https://www.wolframalpha.com/input/?i=integral+from+0+to+1+of+4*a*e%5E%28-2a%29+%2F+%281-e%5E%28-2%29%29%5E2

https://www.wolframalpha.com/input/?i=integral+from+1+to+2+of+4*%282-a%29*e%5E%28-2a%29+%2F+%281-e%5E%28-2%29%29%5E2

If the time "a" of the second fish is between 0 and 1, we want probability of one fish coming in the next hour, and then no fish in the remaining time "1-a". If "a" is between 1 and 2, we want the probability of one fish coming in the remaining time "2-a". These probabilities can be found quickly using the Poisson distribution with rate 2t, where t is the length of the time interval. The integrals could be found below.

https://www.wolframalpha.com/input/?i=integral+from+0+to+1+of+4*a*e%5E%28-2a%29+%2F+%281-e%5E%28-2%29%29%5E2+*+2e%5E%28-2%29+*+e%5E%28-2*%281-a%29%29

https://www.wolframalpha.com/input/?i=integral+from+1+to+2+of+4*%282-a%29*e%5E%28-2a%29+%2F+%281-e%5E%28-2%29%29%5E2+*+e%5E%28-2%282-a%29%29*2*%282-a%29

However, I simulated this question and find the answer to be around 0.142, while adding those two integrals and then even multiplying by the probability the first two interarrivals are less than 1, which is (1-e^(-2))^2, gives me an answer that is different.

How would I go about doing this more elegantly, since I would imagine there is a better solution that is actually correct? Sorry for the long post but wanted to provide my approach in case someone can tell me what is incorrect.

答: You need to evaluate the following probability: $$P(X_2 \leq 1, X_3 \leq 1,T_3\leq2,T_4>2)$$ Here, $X_1$ is the arrival time of the first fish, $X_2$ is the interarrival time between the first and second fish, $X_3$ is the interarrival time between the second and third fish, $T_3=X_1+X_2+X_3$ is the arrival time of the third fish, and $T_4$ is the arrival time of the fourth fish. Notice here we're allowing this Poisson process to continue even in the event that the fisherman leaves so we can discuss the arrival of the $4^{\text{th}}$ fish. Using the total law of probability we can express this probability as $$\int_0^2P(X_2\leq1,X_3\leq1,X_4>2-t|T_3=t)f_{T_3}(t)dt$$ where $X_4$ is the interarrival time between the third and forth fish and $f_{T_3}(t)=4t^2e^{-2t}$ is the pdf of $T_3$. Using independence we can simplify this expression a little bit: $$\int_0^2P(X_2 \leq 1,X_3 \leq 1|T_3=t)P(X_4>2-t)f_{T_3}(t)dt$$ We know $X_4\sim \text{Exponential}(2)$ so $P(X_4>2-t)=\int_{2-t}^{\infty}2e^{-2x}dx=e^{2t-4}$ and this probability becomes $$\frac{4}{e^4}\int_0^2t^2P(X_2\leq 1,X_3 \leq 1|X_1+X_2+X_3=t)dt$$ Clearly $P(X_2\leq 1,X_3\leq 1|X_1+X_2+X_3=t)=1$ whenever $t\leq 1$, but how do we handle the case when $t\in(1,2]$? Here's how I did it. Suppose $(X,Y,Z)\sim f_{XYZ}$ is a trivariate random vector supported on $(0,\infty)^3$ with pdf $$f_{XYZ}(x,y,z)=8e^{-2(x+y+z)}$$ Observe how $$f_{XYZ}(x,y,z)=f_{X_1}(x)f_{X_2}(y)f_{X_3}(z)$$ We can evaluate $P(Y\leq 1,Z\leq 1|X+Y+Z=t)$ using surface integration. When $t\in(1,2]$ this equals $$\frac{I_1 + I_2}{\int_0^t \int_0^{t-x}\sqrt{3}f(x,y,t-x-y)dydx}$$ where $$I_1=\int_0^{t-1} \int_{-x+t-1}^1\sqrt{3}f(x,y,t-x-y)dydx \\ I_2=\int_{t-1}^t \int_0^{-x+t}\sqrt{3}f(x,y,t-x-y)dydx$$ This evaluates to $\frac{4}{t}-\frac{2}{t^2}-1$ so the probability you catch three fish in two hours equals $$\frac{4}{e^4}\Bigg[\int_0^1 t^2dt + \int_1^2 (-t^2+4t-2)dt\Bigg]=\frac{8}{e^4}\approx 0.147$$


问:
How many $k$-letter words are there such that the letters A and B are not next to each other?
I spent the better part of a long car ride today thinking about the following problem:

Consider an alphabet of $n$ letters. How many $k$-letter words of this alphabet are there such that two certain letters (say A and B) are not next to each other? A word may contain the same letter multiple times.

My thoughts: There are $n^k$ words with length $k$ over the alphabet. We need to find and subtract away the number of words where A and B are next to each other. I modeled any such word as one with the string AB or BA at an index $i$:

$$x_1x_2x_3\cdots x_{i-1}ABx_{i+2}\cdots x_k$$

The $x_j$ here are all letters of the alphabet. We can think of the above word as an $(i-1)$-letter word, followed by AB, followed by a $(k-i-2)$-letter word. Thus, there are $n^i \cdot n^{k-i-2} = n^{k-2}$ words where AB or BA is at an arbitrary index $i$. Summing over all $i$, we get that there are $(k-2)n^{k-2}$ words containing AB and $2(k-2)n^{k-2}$ words containing AB or BA. Our final expression for the number of $k$-letter words such that A and B are not adjacent is

$$n^k - 2(k-2)n^{k-2}$$

There’s an issue though. I’m over-counting words that contain AB or BA by a lot. I ran a simulation, and at $n=k=10$, for example, the correct value is $8441614754$, and my answer is $8400000000$. By this method, any word that contains AB or BA more than once is counted more than once. Is there any way I can modify this approach to yield the correct result? If not, how should I proceed?

答:
You can handle this with coupled recurrences.  Let $A(k)$ be the number of words without $AB$ or $BA$ that end in a character other than $A$ or $B$.  Let $B(k)$ be the number of words without $AB$ or $BA$ that end in $A$ or $B$.  You can add any character to an $A(k)$ word, but only $n-1$ characters to a $B(k)$ word, one of which leaves it as a $B(k+1)$ word.  The recurrences are
$$A(k+1)=(n-2)A(k)+(n-2)B(k)\\
B(k+1)=2A(k)+B(k)\\
A(0)=1\\
B(0)=0$$
For small $k$ you can make a spreadsheet to do these.  For large $k$ you can do the eigenvalue/eigenvector thing on the matrix $$\begin {pmatrix} n-2&n-2\\2&1 \end {pmatrix}$$
The leading eigenvalue is $\frac 12\left(\sqrt{n^2+2n-7}+n-1\right)\approx n$ when both $k$ and $n$ are large.  You want $A(k)+B(k)$
I made a spreadsheet for $n=10$, shown below.  In the line for $n=2$ the $98$ under $A+B$ shows there are $98$ two character strings that are not $AB$ or $BA$.  As there are $10^2=100$ unrestricted strings and we rule out $2$, this is correct.  The $18\ B$ strings have one of $9$ characters (not a $B$) then an $A$, or one of $9$ characters (not an $A$) then a $B$.


问:
Area of triangle with incircle tangent to semicircle whose diameter is on one triangle side
Triangle $\triangle ABC$ with incenter $I$ and inradius $r$ has the following property: the incircle is tangent to the semicircle with diameter $AB$ and is within the semicircle. Find the area of $\triangle ABC$ as a function of the side $AB$ and the inradius $r$.

So far I've noticed that $\angle AEF=\angle BEF=\frac{\pi}{4}$ but I don't think that that's useful in any way.

答:
Lemma.
$$|\triangle ABC|=\frac12ch=\frac{c^2r}{c-c'} \qquad\qquad
\left(\;\leftarrow\quad\frac{h}{c}=\frac{h-2r}{c'}\;\right)\tag1$$

Therefore, to get the formula derived in other answers, "all we have to do" is show that the particular circumstances of the original problem imply that $c'=r$. We can do this by focusing on the tangential trapezoid $\square ABB'A'$ and introducing a concentric semicircle.

From the three shaded right triangles in the figure (two determined by angle-chasing, one via Thales' Theorem), we observe three instances of the geometric mean construction, whence

$$r^2 = pp' = qq' = (p-r)(q-r) \tag{2}$$

Then we have
$$(p-r)(q-r)=r^2\quad\to\quad pq=r(p+q) \quad\to\quad \frac1r=\frac1p+\frac1q =\frac{p'+q'}{r^2} \tag3$$

Thus, $c' := p'+q' = r$, as desired. $\square$


问:
Prove that $n\left(n(n-3)+8\right)$ is divisible by 3
The following expression seems to result in an integer for all $n$:
$$\frac13n\left(n(n-3)+8\right)$$
So, how do I prove that, if $n$ is not a multiple of $3$, $n(n-3)+8$ is.

Body:
$$\frac13n\left(n(n-3)+8\right)=\frac13n\left(n^2-3n+8\right)\\=\frac13n\left(n^2-3n+2+6\right)=\frac13n\left((n-1)(n-2)+6\right)\\=\frac13n(n-1)(n-2)+2$$
One of $n,\ n-1, \ n-2$ is divisible by $3$.


问:
Solve Linear Least Squares with Squared $ {L}_{2} $ Norm Regularization (Tikhonov / Ridge Regression) with Non Negativity Constraint Using FASTA
The open source optimization library FASTA (Fast Adaptive Shrinkage/Thresholding Algorithm) is an efficient, easy-to-use implementation of the proximal gradient method for regularized optimization problems. Embeded solvers could solve LASSO, Ridge Regression and Matrix Complementry problems.

I want to solve the following problem using FASTA:
$$\arg \min_x \{||Ax-b||^2+\lambda||x||^2 \} \\ s.t.\quad  x\ge 0$$

Acordding to the follwing LASSO solver(in MATLAB):

```<code>%%  Define ingredients for FASTA
%  Note: LASSO solver solves min f(Ax)+g(x).
%  A and b are given.
%  f(z) = .5 ||z - b||^2
f    = @(z) .5*norm(z-b,'fro')^2;
grad = @(z) z-b;
% g(z) = 0 for all feasible z, and infinity otherwise.  However, iterations
% always end with a feasbile z, so we need not consider the infinity case.
g = @(x) 0;
% proxg(z,t) = argmin t*mu*|x|+.5||x-z||^2
prox = @(z,t) project_1ball(z,mu);

%% Call solver
[solution, outs] = fasta(A,At,f,grad,g,prox,x0,opts);
</code>```

I write the following nonnegative constraned Ridge Regression Solver:

```<code>%%  Define ingredients for FASTA
%  Note: fasta solves min f(Ax)+g(x).
%  f(z) = .5 ||z - b||^2
f    = @(z) .5*norm(z-b,'fro')^2;
grad = @(z) z-b;

g = @(x) 0.5*mu*norm(x,'fro')^2;
prox = @(x,t) mapping(x,t*mu);

%% Call solver
[solution, outs] = fasta(A,At,f,grad,g,prox,x0,opts);

%% Embeded function
function x = mapping(x,tau)
    x = x+tau;
    x(x<0) = 0;  % for non-negative constraint
end
</code>```

But it did not converge.
How to solve the NON-NEGATIVE constrained ridge regression problem using FASTA?

答:
Let's say you want to minimize $\frac12 \| Ax - b \|^2 + \frac{\lambda}{2} \| x\|^2$ subject to the constraint that $x \geq 0$ using the proximal gradient method or an accelerated proximal gradient method. The simplest way to do this is to express your problem as minimizing $f(x) + g(x)$, where $f(x) = \frac12 \| Ax - b \|^2 + \frac{\lambda}{2} \| x\|^2$ and $g$ is the indicator function for the nonnegative orthant. The gradient of $f$ is
$$
\nabla f(x) = A^T(Ax - b) + \lambda x.
$$
The proximal operator of $g$ projects onto the nonnegative orthant: $\text{prox}_{tg}(x) = \max(x,0)$.
(The maximum is interpreted component-wise.)

An alternative approach is to express your problem as minimizing $F(x) + G(x)$,
where $F(x) = \frac12 \| Ax - b \|^2$ and $G(x) = \frac{\lambda}{2}\| x \|^2 + I_{\geq 0}(x)$. Here $I_{\geq 0}$ is the indicator function for the nonnegative orthant. The gradient of $F$ is $\nabla F(x) = A^T (Ax - b)$. To evaluate $\text{prox}_{tG}(\hat x)$, we must minimize $\frac{\lambda}{2} \| x \|^2 + \frac{1}{2t} \| x - \hat x \|^2$ subject to the constraint that $x \geq 0$.
Completing the square, this is equivalent to minimizing $\| x - \frac{\hat x}{\lambda t + 1} \|^2$ subject to the constraint that $x \geq 0$. The minimizer is
$$
\text{prox}_{tG}(\hat x) = \max \left( \frac{\hat x}{\lambda t + 1} , 0 \right).
$$
Note that this disagrees with the proximal mapping given in your code, which is probably the reason the algorithm failed to converge.


问:
Understanding sum of Dirichlet characters
I'm trying to understand how Dirichlet Characters work, especially the sum of Dirichlet Characters.
Concerning the definitions, we have:
$\chi : G \longrightarrow \mathbb{C} ^{\times}$ is a homomorphism from a group $G$ to $\mathbb{C} ^{\times}$. These homomorphisms are called characters of $G$. $\widehat{G}$ denotes the set of all characters of $G$.

Now, is it given that $G$ is always cyclic, or are there cases where $G$ is not cyclic?

I have a lemma in my textbook (Multiplicative Number Theory I. Classical Theory by Montgomery H.L., Vaughan R.C., lemma 4.2, page 115) that states that for $G$ cyclic og order $n$, and $G$ generated by $a$, there are exactly $n$ characters of $G$, namely $\chi_k(a^m)=e(km/n)$ for $1\leq k \leq n$. But it's not clear to me what the expression $e(km/n)$ means. This is important for me to understand in order to show the rest of the lemma, which states:

$\sum_{g\in G}\chi (g) = \{n \text{ if } \chi=\chi_0 \text{ and } 0 \text{ otherwise }\} $

and

$\sum_{\chi \in \widehat{G}}\chi (g) = \{n \text{ if } g=e \text{ and } 0 \text{ otherwise }\} $

$\chi_0$ is the principal character.

If someone knows an easy-to-understand introduction to Dirichlet Characters, please point me in that direction.

答:
Let $\chi$ be an arbitrary character of $G$ and $a$ be $G$'s generator, then we have

$$
\chi(a^n)=1=\chi(a)^n
$$

Since $\chi$ is a homomorphism from $G$ into the complex domain, we know that the above equation has $n$ solutions, each of them being the $n$'th root of unity. Thus using the notation $e(s)=e^{2\pi is}$ we can rewrite the character as

$$
\chi_k(a)=e(k/n)
$$

where $k=0,1,2,\dots,n-1$. This indicates that there are exactly $n$ characters in a cyclic group of order $n$. Moreover, we know that the character maps the group into the unit circle of complex plane.


问:
How did the approximation $\left(1+\frac{h}{R}\right)^{-2} \approx 1-\frac{2h}{R}$ come about?
In physics there is a formula calculate the variation in the acceleration due to gravity at a height, it is given by:

$$g=g_0\left(1+\frac{h}{R}\right)^{-2}$$

But it is approximated as $$g=g_0\left(1-\frac{2h}{R}\right)$$

Some how the terms in the brackets are almost equal could anyone show why ?

答: Even without knowing the binomial series or approximations, this can be shown via geometric series:  recall $$f(z) = \frac{1}{1-z} = 1 + z + z^2 + \cdots, \quad |z| < 1,$$ so that $$\frac{1}{(1-z)^2} = (1 + z + z^2 + \cdots )^2 = 1 + 2z + 3z^2 + \cdots.$$  Then with the choice $z = -h/R$, we have $$\left(1 + \frac{h}{R}\right)^{-2} = 1 - \frac{2h}{R} + \frac{3h^2}{R^2} - \cdots.$$  The approximation improves as $h/R \to 0$.


问:
Asymptotic behavior of many derivatives
To compute the residue of a pole of very high order $M$ at $z=0$, one needs to compute

$\frac{d^M}{dz^M} g(z)$

Suppose that $g(z)$ is a reasonable but not trivial function, that itself may depend on $M$. At the moment I'm interested in

$g(z) = \left(\frac{f(z)}{h(z)}\right)^{\gamma-k M}$

where $f(z)$, $h(z)$ are polynomials, and $\gamma$ and $k$ are rational but not integers, but I would like to generalize later.

Are there any tricks to get the asymptotic behavior for this quantity?

I know the following:

(1) I can Laurent expand everything in sight, collect sums and pick out the $M^{th}$ term. This works but then appears to require a lot of Stirling approximations to see the dominant terms.

(2) In principle, I could find the Fourier transform of $g$ and look at its large $q$ behavior. This looks intractable, but would at least allow saddle-point methods to be applied.

答:
A general method is to use Cauchy's integral formula

$\frac{d^M}{dz^M}g(z) = \frac{M!}{2\pi i}\oint_\gamma \frac{g(w)}{(w-z)^{1+M}}$,

where $\gamma$ is a curve encircling $z$ in the anticlockwise direction. For large $M$ the saddle-point method effectively extracts the leading behaviour.

For example, if $g(z)=F(z)^{kM}$, then the saddle-point equation is
$0 = \frac{d}{dw} [k\log F(w)-\log(w-z)] = k \frac{F'(w)}{F(w)} - \frac{1}{w-z}$

and to leading nontrivial exponential order (in M) we have

\begin{align}\log\frac{d^M}{dz^M}g(z) & \sim \log\left[ \frac{M!}{2\pi i} g(w_*)(kF'(w_*)/F(w_*)^M \right] + O(1) \\
& \sim M \log (M/e) - M \log k + M(k-1) \log F(w_*) + M \log F'(w_*) + O(1)
\end{align}
where $w_*(z)$ is the saddle point. If there are multiple saddle points, we should sum over all of them, in principle also checking that the integration path $\gamma$ can be continuously deformed to go through them in the correct orientation.

Title: Asymptotic behavior of many derivatives


答:
For small $\frac hR$, ignore the terms of $(\frac hR)^2$ below

$$\left(1+\frac{h}{R}\right)^{-2}
= \frac1{1+\frac{2h}{R}+( \frac{h}{R})^2}
\approx  \frac1{1+\frac{2h}{R}}
= \frac{1-\frac{2h}{R}}{1-(\frac{2h}{R})^2}
\approx 1-\frac{2h}{R}
$$

Title: How did the approximation $\left(1+\frac{h}{R}\right)^{-2} \approx 1-\frac{2h}{R}$ come about?

Body:
In physics there is a formula calculate the variation in the acceleration due to gravity at a height, it is given by:

$$g=g_0\left(1+\frac{h}{R}\right)^{-2}$$

But it is approximated as $$g=g_0\left(1-\frac{2h}{R}\right)$$

Some how the terms in the brackets are almost equal could anyone show why ?


问:
Prove that for $f(x) = \frac{x^\textrm{T}Ax}{x^\textrm{T}x}$ and any $v$, $v^\textrm{T}Hv=0$
$f(x) = \frac{x^\textrm{T}Ax} {x^\textrm{T}x}$, where $A$ is a symmetric $n \times n$ matrix and $x \neq 0$. I need to prove that if $H=H(f)(v)$, where $H(f)(v)$ is the Hessian of function $f$ evaluated for vector $v$, $v^\textrm{T}Hv=0$ for any $v$.

I have already proved that:

(a) $\frac{df}{dx}=0$ iff $x$ is an eigenvector of $A$;

(b) $f(cx) = f(x)$ for $c \in R$;

(c) $\lambda_\min \leq f \leq \lambda_\max$ where $\lambda_\max$ and $\lambda_\min$ are the maximal and minimal eigenvalues of $A$.

The hint to the question states the following: “ Hint: do not attempt to calculate the Hessian directly: the algebra is very messy. Use
the intuition gave by (b), that a certain function is constant.”

答:
$\newcommand{\R}{\Bbb{R}}\newcommand{\x}{\mathbf{x}}\newcommand{\a}{\mathbf{a}}\newcommand{\y}{\mathbf{y}}\newcommand{\v}{\mathbf{v}}$You can do this by using some facts from multivariable calculus.

Fix $\v \in \R^n$. Let $\phi:\R \to \R$ be defined by $\phi(c)=f(c\v)$. By part (b), we know that $\phi$ is constant, so $\phi'(c)=0$ and $\phi''(c)=0$ for all $c\in \R$.

The result will now follow by doing some multivariable calculus computations to show that in fact $\phi''(c) = \v^T (H(f)(c\v))\v$ (then putting $c=1$).

Firstly, note that
$$\begin{align*}
\phi'(c) &= D_c (f(c\v))\\
&= \v^T \nabla f(c\v) \quad (\text{using fact 1 from the bottom})
\end{align*}
$$

where $\nabla f(\x)$ is the gradient vector of $f$ evaluated at $\x$ and is expressed as a column vector.

Therefore, we have

$$\begin{align*}
\phi''(c) &= D_c (\v^T \nabla f(c\v))  \\
&= \v^T \left( D_c  \nabla f(c\v)\right) \quad (\text{using fact 2 from the bottom})\\
&= \v^T \left( (H(f)(c\v)) \v\right) \quad (\text{ using fact 3 and multivariable  chain rule}) \\
&= \v^T (H(f)(c\v)) \v.
\end{align*}
$$

Put $c=1$ and recall that $\phi''(1)=0$ to get the desired result.

A summary of the multivariable calculus facts used is given below.

If $h:\R^{n}\to\R^{m}$, then denote by $D_{\x} (h)$ ("the Jacobian of $h$") the $m\times n$ matrix whose $i,j$ entry is equal to $\dfrac{\partial h_i}{\partial x_j}$ for $i=1,\ldots,m$ and $j=1,\ldots,n$. (Here $h(\x) = \begin{bmatrix} h_1(\x) \\ \vdots \\ h_m(\x)\end{bmatrix}$ where $h_i:\R^n \to \R$ are the components of $h$ and $\x =  \begin{bmatrix} x_1 \\ \vdots \\ x_n\end{bmatrix} \in \R^n$.) If we evaluate the Jacobian at a point $\a\in \R^n$, we may denote this as $D_{\x} (h)(\a)$ or $D_{\x} (h(\a))$.

The multivariable chain rule tells us that if $h:\R^{n}\to\R^{m}$ and $g: \R^{p}\to\R^{n}$, with the composite function $h\circ g : \R^p \to \R^m$, denoting $\y = g(\x)$ where $\x\in \R^n$ and $\y\in\R^p$, we have $D_{\x}(h\circ g) = (D_{\y} h)(D_{\x} g)$ (matrix product). Note in this formula, if $D_{\x}(h\circ g)$ is evaluated at $\a\in \R^p$, then $D_{\y} h$ should be evaluated at $\mathbf{b} = g(\a)\in \R^n$ and $D_{\x} g$ should be evaluated at $\a\in\R^p$.

I leave as an exercise to you to show the following facts (with some hints), which were used in some form above:

Fact 1. Let $f:\R^n\to \R$ and $\v$ a fixed vector in $\R^n$. Let $\phi:\R\to \R, \quad \phi(c)=f(c\v)$. Then $(D_c \phi) (c)\equiv \phi'(c) = \v^T \nabla f(c\v)$, where $\nabla f(c\v)$ is the gradient vector of $f$ evaluated at $c\v$. (Use multivariable chain rule to show this.)

Fact 2. (Derivative can "move inside" product with fixed matrix) Let $h:\R^n\to \R^m$ and $B$ be a fixed $p\times m$ matrix. Let $g:\R^n \to \R^p$ be given by $g(\x) =  B h(\x)$ for $\x\in \R^n$. Then $D_{\x} g = B \left(D_{\x} h\right)$. (You can show this very easily using the multivariable chain rule.)

Fact 3. (Hessian of a function is equal to Jacobian of gradient) Let $f:\R^n\to \R$ be a twice continuously differentiable function. Then $H(f)(\x) = D_{\x}(\nabla f(\x))$ for all $\x\in \R^n$.


问:
Why does the set of submodules of a module that are direct sums of irreducible submodules have a maximal element?
I was reading the proof that every R-module M of an artinian semisimple ring R is the direct sum of all irreducible R-submodules M. In the proof they stated that the set
$$\mathcal{F}:=\{N\subset M: N \text{ is the direct sum of its irreducible submodules}\}$$
has a maximal element. I was trying to see why such a maximal element exists.

My attempt: Let $\{N_i\}_{i\in I}\subset \mathcal{F}$ be a total ordered subset of $\mathcal{F}$ ($I$ is any indexation set). I want to prove that $N=\cup_{i\in I} N_i$ belongs to $\mathcal{F}$. We know that for each $i\in I$ there's an indexation set $J_i$ such that $N_i=\bigoplus_{k_i\in J_i} M_{k_i}$ with $M_{k_i}$ irreducible submodules of $N_i$. Define $$\Lambda :=\cup_{i\in I}\{k_i\in J_i:M_{k_i}=M_{k_{io}} \text{ for some }i_o\in I\setminus\{i\} \text{ and } k_{i_o}\in J_{i_o}\}$$

Obviously $\sum_{k_i\in (\cup_{i\in I} J_i)\setminus \Lambda} M_{k_i}$ is direct sum, but I got stuck for adding only one time such irreducible submodules $M_{i_k}$ associated to $\Lambda$ to asure the direct sum.

答:
In fact, the set $\mathcal{F}$ is closed under the union of any chain. Let $\{N_i\}_{i\in I}\subset \mathcal{F}$ a total ordered subset of $\mathcal{F}$. Clearly $M=\cup_i N_i$ is a sum of irreducible $R$-modules. Write $M=\sum_{j\in J} T_j$ with $T_j$ irreducible modules. Let $\mathcal{S}\subset \mathcal{P}(J)$  such that for all $S_o\in \mathcal{S}$, $\sum_{s\in S_o}T_s=\bigoplus_{s\in S_o}T_s$. $S$ is not empty because for each $j\in J$, $\{j\}\in \mathcal{S}$. Let's see that $\mathcal{S}$ has a maximal. Let $\{S_r\}$ be a total ordered subset of $\mathcal{S}$ and let $\hat{S}=\cup_r S_r$. Pick any $s_o\in\hat{S}$ and  $x\in T_{s_o}\cap\sum_{s\in\hat{S}\setminus\{s_o\}} T_s$. Then $x=x_{s_1}+\cdots+x_{s_{n}}$ with $x_{s_l}\in T_{s_l}$. Since $\{S_r\}$ is a chain, there's $n_o\in\{1,\ldots,n\}$ such that $x_{s_l}\in T_{s_{n_o}}$ for all $l\in\{1,..,n\}$. Then $x\in T_{s_o}\cap T_{s_{n_o}}$. Since each $T$ is irreducible, $x=0$. Conclution $\mathcal{S}$ has a maximal, call it $S_o$.

Finally, let's prove that $M=\bigoplus_{s\in S_o} T_s$. Clearly $\bigoplus_{s\in S_o} T_s\subset M$. Suppose that there's $x\in M\setminus\bigoplus_{s\in S_o} T_s$ with $x\neq 0$. Then, $x\in T_p$ for some $p\in J$ with $p\notin S_o$. It's easy to check that $\sum_{s\in S_o\cup\{p\}}T_s=\bigoplus_{s\in S_o\cup\{p\}}T_s$. This contradicts the maximality of $S_o$. Hence $M$ is a direct sum of irreducible modules, i.e., it's the direct sum of all its irreducible submodules.


问:
Proving a statement about $k$-colouring of a graph

Prove that a graph is $k$-colourable iff its edges can be oriented in such a way that the resulting directed graph does not contain a path of length $k$.

It seems to me that the '$\Leftarrow$' implication might be slightly easier to show if we were to consider directed acyclic graphs (then we could assign subsequent colors to vertices as we traverse along a path and do some rearranging when we visit an already coloured vertex)... But I am stuck at finding a valid argument that justifies the implication in either direction, not to mention I am actually interested in a stronger statement.

答: For the forward direction, let the colors be $\{1,2,\ldots, k\}$ and orient each edge to go from the higher color to the lower one.</p>


问:
Laplace transform $ \mathscr{L} \left( \int_0^t \frac{e^{-\tau}-1}{\tau}d\tau \right) $
Can anyone give me a hint to solve

$$
\mathscr{L}  \left( \int_0^t \frac{e^{-\tau}-1}{\tau}d\tau \right)
$$

答:
First try finding the laplace transform of this function:

\begin{equation*}
\frac{e^{-t} -1}{t}
\end{equation*}

Using the rule:

\begin{equation*}
L\left(\frac{f( t)}{t}\right) =\int ^{\infty }_{s} g( s)
\end{equation*}
where

\begin{equation*}
L( f( t)) =g( s)
\end{equation*}
then try using the rule

\begin{equation*}
L\left(\int ^{t}_{0} f( t) dt\right) =\frac{g( s)}{s}
\end{equation*}
I thin this should lead you where you want.


问:
Is XOR-SAT + $2$-SAT in P?
I read in a paper a proof where you can reduce a $3$-SAT problem into $2$-SAT + HORN-SAT clauses.

$2$-SAT + HORN-SAT is therefore, NP-complete.

$2$-SAT, HORN-SAT, DUAL HORN-SAT, XOR-SAT are all in P.

I would like to know, if there is a Polynomial time algorithm for the conjuntion of $2$-SAT and XOR-SAT formulas.

答:
There is no polynomial-time procedure for deciding the satisfiability of 2-SAT + XOR-SAT unless P = NP.  So, probably not.  2-SAT + XOR-SAT is easily proven NP-complete by direct polynomial reduction from 3-SAT.

In a 3-SAT instance, each 3-CNF clause $$(x_1 \lor x_2 \lor x_3)$$ can be rewritten into the equisatisfiable 2-SAT + XOR-SAT expression $$(x_1 \lor \overline{y}) \land (y \oplus x_2 \oplus z) \land (\overline{z} \lor x_3)$$ with $y$ and $z$ as new variables that appear nowhere else in the formula.

Title: Is XOR-SAT + $2$-SAT in P?


问:
Eigenvalues of a symmetric positive definite matrix multiplied by a diagonal matrix
Let $A \in \mathbb{R}^{n \times n}$ be a positive definite matrix and $D = \text{diag} (d_1, d_2, ... , d_n)$ be a positive diagonal matrix.
We know that eigenvalues of A are $\lambda_1 \leq \lambda_2 \leq ... \leq \lambda_n$.
What will be eigenvalues of $DAD$? (Obviously they're all positive.)</p>

答:
You do have in general inequalities for singular values of the product of two matrices $M$, $N$, due to Weyl or Schur, I forgot, Horn and Johnson should have the reference. If $\alpha_i$, $\beta_i$ $\gamma_i$ are the singular values of $M$, $N$ and $MN$, in decreasing order then
$$\alpha_1 \cdot \beta_1\ge \gamma_1  \\
 \alpha_1 \alpha_2 \cdot \beta_1 \beta_2\ge \gamma_1 \gamma_2\\
\ldots\ldots\ldots\\
\alpha_1 \cdots\alpha_n \cdot\beta_1 \cdots \beta_n = \gamma_1 \cdots \gamma_n$$
The first inequality is not hard, since it is the inequality for the $l^2$ norm. The other are obtained considering the associated operators $\wedge^k M, N, MN$.

So, fixing $\lambda_i$ for a hermitian, and the $d_i$ there definitely are inequalities for the eigenvalues of $DAD$. Hard to tell what are all the defining inequalities.


问:
How do we prove That $\mathbb{P}(A\cap B) - \mathbb{P}(A)\mathbb{P}(B)\leq 1/4$?
How do we prove That $\mathbb{P}(A\cap B) - \mathbb{P}(A)\mathbb{P}(B)\leq 1/4$?

I have tried in this way:

\begin{align*}
\begin{cases}
\mathbb{P}(A)\geq \mathbb{P}(A\cap B)\\\\
\mathbb{P}(B)\geq \mathbb{P}(A\cap B)
\end{cases} \Rightarrow \mathbb{P}(A)\mathbb{P}(B)\geq[\mathbb{P}(A\cap B)]^{2}
\end{align*}

But I am unable to prove the required result.

答:
HINT

Since $A\cap B\subseteq A$ and $A\cap B\subseteq B$, due to the monotonicity of the probability measure, we conclude that
\begin{align*}
\mathbb{P}(A\cap B) \leq \min\{\mathbb{P}(A),\mathbb{P}(B)\}
\end{align*}

Without loss of generality, we can assume that $\mathbb{P}(A)\leq\mathbb{P}(B)$. Consequently, one has that
\begin{align*}
\mathbb{P}(A\cap B) - \mathbb{P}(A)\mathbb{P}(B) \leq \mathbb{P}(A) - \mathbb{P}(A)\mathbb{P}(B) = \mathbb{P}(A)\mathbb{P}(B^{c}) \leq \mathbb{P}(A)\mathbb{P}(A^{c}) = \mathbb{P}(A)(1 - \mathbb{P}(A))
\end{align*}

where the last relation comes from the fact that
\begin{align*}
\mathbb{P}(A) \leq \mathbb{P}(B) & \Longleftrightarrow 1 - \mathbb{P}(A) \geq 1 - \mathbb{P}(B) \Longleftrightarrow \mathbb{P}(A^{c}) \geq \mathbb{P}(B^{c})
\end{align*}

Can you take it from here?


问:
Is closure of a semigroup again a semigroup?
Let $S$ be a compact left-topological semi-group (meaning, $S$ is both a semi-group and a compact Hausdorff topological space, and the map $x \mapsto x y$ is continuous for any fixed $y$, but the map $y \mapsto xy$ may not be continuous).

Consider $T_0 \subset S$ which is a sub-semigroup, but is not necessarily compact. A rather straightforward application of Kuratowski-Zorn shows that there exists a minimal compact sub-semigroup $T$ of $S$ which contains $T_0$. Wishful thinking suggests that $T = \overline{T}_0$, and this would be right and easy to show, if only multiplication was continuous in both arguments. It would also work under the assumption that $T_0$ is commutative.

I do not believe this is true in general, but I can't see an easy counterexample. Could somebody be so kind as to present one? Of course, if it is generally true that $T = \overline{T}_0$, then I would be even happier and more grateful!

答:
Promoting the comments to an answer:

tomasz points out that we have $$T = \bigcap \{G \mid G \supseteq T_0 \text{ is a closed subsemigroup of }S\} \supseteq \overline{T}_0.$$

The semigroup $S = \operatorname{Fun}(X,X)$ of all functions $f \colon X \to X$ on a topological space $X$ is a left-topological semigroup under composition when equipped with the topology of pointwise convergence, i.e., the product topology $X^X$. Observe that $g \mapsto fg$ is continuous if and only if $f$ is continuous, so on a non-discrete $T_1$ space $S$ is not a right topological semigroup.

Martin Sleziak remarks that Arhangel'skii-Tkachenko provide the following counterexample in Topological groups and related structures (example 1.4.11).

Consider the one-point compactification $X = \mathbb{N} \cup \{\infty\}$ of the natural numbers. Then $S = \operatorname{Fun}(X,X)$ is a compact left-topological semigroup.

Let $T_0 \subset S$ be the subsemigroup consisting of injective functions $X \to X$. The functions $f_k$ defined by $f_k(n) = n+k$ for $n \in \mathbb{N}$ and $f_k(\infty) = \infty$ are in $T_0$ and they converge pointwise to the constant function $f(n) = \infty$, so $f \in \overline{T}_0$.

Let $g(n) = n+1$ and $g(\infty) = 1$, so $g \in T_0$. We have $g \circ f_k \in T_0$ and $g \circ f(x) = 1$ for all $x \in X$. Since $g \in T_0 \subseteq T$ and $f \in \overline{T}_0 \subseteq T$ we have that $g \circ f \in T$. Now observe that $g \circ f \notin \overline{T}_0$. Indeed, the set $U = \{s \in S \mid s(1) = 1\text{ and } s(123) = 1\}$ is open in $S$ and disjoint from $T_0$, while $g \circ f \in U$, so $g \circ f \in T \setminus \overline{T}_0$.


答:
You can also use the Mathematical Induction to prove this.

CASE 1 $(n=1)$: So your equation turns out to be $$1(1(1-3)+8)=6=3(2)$$
Thus, when $n=1$, this equation is divisible by $3$.

CASE 2 $(n=m)$: We assume that $m(m(m-3)+8)$ is divisible by $3$.

CASE 3 $(n=m+1)$: The equation in this case becomes:
$$\begin{align}&(m+1)\{(m+1)(m+1-3)+8\}\\
=&(m+1)\{(m+1)(m-2)+8\}\\
=&(m+1)\left(m^2-m+6\right)\\
=&m^3+5m+6\\
=&\underbrace{m(m(m-3)+8)}_{\text{divisible by 3 from CASE 2}}+3\left(m^2-m+2\right)\\
\end{align}$$
Thus, the equation in CASE 3 is also divisible by $3$.

Thus, by the Principle of Mathematical Induction, we can conclude that the equation $n(n(n-3)+8)$ is divisible by $3$ for all $n\in\mathbb{N}$

Title: Prove that $n\left(n(n-3)+8\right)$ is divisible by 3

Body:
The following expression seems to result in an integer for all $n$:
$$\frac13n\left(n(n-3)+8\right)$$
So, how do I prove that, if $n$ is not a multiple of $3$, $n(n-3)+8$ is.


问:
Reduce the Cauchy-Euler equation to a smaller expression?
Given the Cauchy-Euler second order differential equation:
$$ \left( x^2\frac{d^2}{d x^2} + x\frac{d}{d x} -1\right)y(x)=0 $$
is it possible to find a function $u(x)$ , which satisfies the following simple form:?
$$ \frac{d^2 y(u)}{d u^2}=0 $$
***notice that $t=\ln(x)$ yields:
$$ \frac{d^2 y(t)}{d t^2}-1=0 $$

答:
HINT

To begin with, notice that

\begin{align*}
x^{2}y'' + xy' - y = 0 & \Longleftrightarrow (x^{2}y'' + 2xy') - (xy' + y) = 0\\\\
& \Longleftrightarrow (x^{2}y')' - (xy)' = 0\\\\
& \Longleftrightarrow x^{2}y' - xy = c_{0}
\end{align*}

Can you take it from here?


问:
Probability of Consecutive Cards
I've got a deck of 36 cards... 6 are labeled with #1, 6 with #2, and so on up to 6 with #6. I'm drawing 3 cards from the deck & wondering what the probability is that I will end up with 2 or more consecutive cards (including wrap-arounds--meaning a #6 can wrap-around to a #1 and visa-versa).

I know that it's 66.7% WITH replacement as I actually drew the whole thing out on a spreadsheet with every possible outcome (and got 24/36), but I know that the number will increase WITHOUT replacement, and I'm just not sure how to come up with the formula to figure it out.

I came up with this formula... 12/35 + (24/35 x 12/34)+(16/35 x 12/34) = 74.6%, but that seems way too high as I can't see an 8% jump just because I didn't replace 2 cards.

Is there anybody out there who can help me?

答:
Let's count the number of hands which don't contain any consecutive cards.

If all the cards are distinct and there are no consecutive cards, then we have only two possible hands to consider, and they are $\{1,3,5\},\{2,4,6\}$; there are ${2 \choose 1}{6 \choose 1}^3$ ways to get these hands from our deck of $36$. Now if our hand of three cards contains only two distinct numbers and no consecutive cards (like, for example, the hand $\{3,1,1\}$), then we have ${6 \choose 1}{3 \choose 1}{6 \choose 1}{6 \choose 2}$ hands of this type. Since there are ${6 \choose 1}{6 \choose 3}$ hands of three cards that contain only one number, the probability that your hard contains at least two consecutive cards is $$1-\frac{{2 \choose 1}{6 \choose 1}^3+{6 \choose 1}{3 \choose 1}{6 \choose 1}{6 \choose 2}+{6 \choose 1}{6 \choose 3}}{{36 \choose 3}}\approx 0.696$$

Title: Probability of Consecutive Cards


问:
Topological property of continuous functions from $\mathbb{R}^2$ to $\mathbb{R}^2$.
This question is how to prove the following statement:

$$\forall \text{continuous }f:\mathbb{R}^2\to\mathbb{R}^2(\exists \alpha,\beta>0 (\forall a\in(0,\alpha](\forall b\in(0,\beta](f[[0,a]\times[0,b]]\text{ is simply connected}))))$$

Any hint would be helpful.

答:
If you are familiar with the Hawaiian earring you may be able to perceive a counterexample, which I'll describe briefly.

Let $C_n$ be the circle of radius $1/2^n$ in the right half-plane tangent to the $y$-axis at $(0,0)$. Let $C = \bigcup_{n \ge 1} C_n$; this is a version of the Hawaiian earring. One can construct a continuous path $\gamma : [0,1] \to \mathbb R^2$ with image $C$, such that the restricted path $\gamma \mid [2^{-k},2^{-k+1}]$ goes once around the circle $C_k$ at constant speed. Thus, the restriction to $[0,2^{-k}]$ contains infinitely many distinct circles $C_{k+1},C_{k+2},\ldots$ and evidently has non-simply connected image.

Now define $f : \mathbb R^2 \to \mathbb R^2$ by
$$f(x,y) = \begin{cases}
\gamma(x^2+y^2) &\quad\text{if $x^2+y^2 \le 1$} \\
\gamma(1) &\quad\text{if $x^2 + y^2 \ge 1$}
\end{cases}
$$


问:
Can a newton polynomial provide more accuracy than natural cubic splines in some cases?
My assignment is to interpolate the sin function using 10 points of the function with 6 decimal correct places with polynomials and splines. The polynomial interpolation gave me at worst 4 correct decimal places, while the splines gave me at worst 2 correct decimal places. Can that happen given a specific set of points or is my implementation wrong?

Here are the points:

```<code>  x(1, 1) = 0;
  x(2, 1) = 0.203056;
  x(3, 1) = 0.267584;
  x(4, 1) = 0.379246;
  x(5, 1) = 0.527854;
  x(6, 1) = 0.713500;
  x(7, 1) = 0.916740;
  x(8, 1) = 1.087621;
  x(9, 1) = 1.274532;
  x(10, 1) = 1.570796;

  y(1, 1) = 0;
  y(2, 1) = 0.201663;
  y(3, 1) = 0.264402;
  y(4, 1) = 0.370220;
  y(5, 1) = 0.503681;
  y(6, 1) = 0.654484;
  y(7, 1) = 0.793622;
  y(8, 1) = 0.885524;
  y(9, 1) = 0.956434;
  y(10, 1) = 1;
</code>```

答:
If your original function is a polynomial of degree 4 or higher, then polynomial interpolation will give you zero approximation error, but cubic spline interpolation will give a non-zero error. So, in this particular case, the polynomial method will certainly work better.

Polynomial interpolation isn't as bad as many people say, and you shouldn't expect that it will always behave poorly. You'll get oscillation problems if you do interpolation using equally spaced nodes, but not if you use Chebyshev nodes. There's a good discussion of these matters in Trefethen's book, Approximation Theory and Approximation Practice.


问:
Regarding Finite group theory, Core of subgroups, and $\Delta_H(G)$.
This was a challenge question posted by my professor in algebra course last semester, and I've been trying to solve it. I think there is probably a solution online but I couldn't find much information about this challenge.

Let $G$ be a non-trivial finite group, and let $H\le G$ be s.t. $|\text{Core}_G(H)|=1$, where $\text{Core}_G(H):=\underset{g\in G}{\cap}gHg^{-1}$.

Prove that $\Delta_H(G):=G-\underset{g\in G}{\cup}gHg^{-1}$ is nonempty;

Can $\Delta_H(G)$ contain an element of prime power order?

My thought:

I was discussing by case. Case 1: $Z(G)$ is non-trivial; Case 2: otherwise.

In case 1, say we have $x\in Z(G)$ with $x\ne e$. Then $x\notin H$, otherwise, we would have $x\in\text{Core}_G(H)$ which makes $|\text{Core}_G(H)|>1$. Thus $x\in\Delta_H(G)$, as $x\notin gHg^{-1}$ for any $g\in G$. Therefore $\Delta_H(G)$ is nonempty. Moreover, it turns out that $Z(G)\subset\Delta_H(G)$, so there must be an element of prime power order.

I have no clues on how to deal with case 2. I tried to think in terms of conjugacy classes (so $\text{Core}_G(H)$ is the intersection of all conjugacy classes of $h\in H$ and $\Delta_H(G)$ is the set of elements which are not in any conjugacy classes of $h\in H$), but it seems to not lead to a solution.

答:
It is well known that no group can be the union of conjugates of a proper subgroup of finite index. In particular, no finite group can be the union of the conjugates of a proper subgroup. Since we are given that the core of $H$ is trivial, $H\neq G$ so part (1) follows from a counting argument.

For part (2), the answer is "yes, it's possible". To see this, let $p$ be an odd prime, and let $G$ be the nonabelian group of order $p^3$ and exponent $p$, with generators $x$ and $y$ ($G$ is also sometimes called the Heisenberg group of order $p^3$). Then $H=\langle x\rangle$ is a proper subgroup of order $p$, but is not normal. Since it is not normal, it's core must be a proper subgroup of $H$. But $H$ is of prime order, so the core of $H$ is trivial. The union of its conjugates cannot be all of $G$, as discussed above, yet every element of $\Delta_H(G)$ is an element of a $p$-group, hence has order that is a power of $p$ (in fact, equal to $p$).

For $p=2$, take $G=D_4$, the dihedral group of order $8$, $G=\langle r,s\mid r^4=s^2=1, sr=r^3s\rangle$, and let $H=\{e,s\}$. Again, $H$ is not normal but of prime order, hence its core is trivial. Any element in $\Delta_H(G)$, which cannot be trivial, is of order a power of $2$.


问:
Multiplication rule vs conditional probability vs Bayes
I am a bit confused, can you help?

So, let's say I have the task of selecting cards from a deck of playing cards. There are 52 cards total; 50% are red and 50% are black.

The probability of getting a red card is 50%
The probability of subsequently selecting a black card is 26/51 (because 1 card is removed)

But the probability of a red card, given we've already got a black card, I think is:
p(A∩B) = p(A) * p(B|A) - Which would be 0.5 * 0.51

But then I hear about a different formula for conditional probabiltiy, where I should divide the result by the probability of selecting a black.

I am confused, as I watched a youTube video which explained that the multiplication rule works like I have it & then read some blogs about dividing by the p(b).

Can someone help me figure out why we do that & whether my initial view was correct?

Thanks a lot

答:
"...the probability of a red card, given we've already got a black card, is $P(A\cap B)=\dots$."

No. $P(A\cap B)$ is the probability of getting a red card and then getting a black card (or getting a black card and then getting a red card). The probability of getting a red card, given we've already got a black card is a conditional probability, denoted $P(A\mid B)$, and calculated by $$P(A\mid B)={P(A\cap B)\over P(B)}$$ In your example, $P(A\cap B)=(26/52)(26/51)=13/51$, while $P(A\mid B)=P(A\cap B)/P(B)=(13/51)/(26/52)=26/51$.


问:
Show that $[l_1 \cdot l_2 \cdot l_3 ] = [l_1 + l_2 + l_3] \in H_1(X)$ The first Homology group of X
Let $l_1$ , $l_2$ and $l_3$ be three paths in X with $l_1 (0) =
l_3 (1)$, $l_1 (1) = l_2 (0)$ and $l_2 (1) = l_3 (0)$. Define the loop $l = l_1 \cdot l_2 \cdot l_3 $ (based at $l_1 (0)$).

Show that $l$ and $l_1 + l_2 + l_3$ are 1-cycles. (This can just be shown by applying the boundary map, $\partial$, on the paths are to get $0$. Hence they are in $\ker(\partial)$, which defines them as 1-cycles).

Furthermore, show that $[l] = [l_1 + l_2 + l_3] \in H_1(X)$

My confusion is regarding treating this as an algebraic problem, or proving it through the definition of homotopy equivalence, i.e using the definition of the class $[l]$ as everything homotopy equivalent to the path $l$

答:
What you are asked to show, namely that $[l] = [l_1 + l_2 + l_3]$ in $H_1(X)$, means precisely that $$l_1+l_2+l_3-l=\partial(\text{something})$$ where $\text{something}\in C_2(X)$, the free abelian group on the set of singular $2$-simplices. That is, you will need to define certain maps $\Delta^2\to X$ and a linear combination of them ($\in C_2(X)$) whose boundary is $l_1+l_2+l_3-l$. Below is a photograph of a drawing of a solution.

The drawing represents two continuous maps $x,y:\Delta^2\to X$. They are constructed as follows: on the boundary $\partial\Delta^2$ they are defined using the paths $l_1,l_2,l_3$, and in the interior, they are defined to be constant along the lighter lines I drew inside the triangles, equal to whatever value they take on the border $\partial \Delta^2$. The vertices of $\Delta^2$ are numbered $0,1,2$ to indicate how the border is calculated.


问:
Showing that degree of polynomial reduced modulo $p$ divides degree of splitting field
Let $f$ be a polynomial of degree $n$ with integer coefficients and $p$ a prime for which $f$, considered modulo $p$, is a degree-$k$ irreducible polynomial over $\mathbb{F}_p$. Show that $k$ divides the degree of the splitting field of $f$ over $\mathbb{Q}$.

(this is Miklos Schweitzer 2020, Problem 10)

My miscellaneous thoughts: We know that for a polynomial of degree $n$, the degree of its splitting field is at most $n!$ from induction on the Ring Tower Theorem. Additionally, since $f(x)$ is irreducible over $\mathbb{F}_p$, then the field $\mathbb{F}_p[x]/(f(x))$ has a root of $f(x)$. Now suppose $k = 2$. Then $f(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0 \in \mathbb{Z}[x]$ reduces to $f(x) \equiv b_2 x^2 + b_1x + b_0 \in \mathbb{F}_p [x]$ where $b_i \equiv a_i \pmod{p}$ where applicable. I'm really not sure if these things are particularly useful or how to combine them.

This is really hard!

答:
Cool problem! Here is a solution, which I preface with a hint/sketch, in case anyone reading wants to try to finish it for themself.

First fix some notation: let $\overline{f}$ be the reduction of $f$ mod $p$, $K/\mathbb{Q}$ the splitting field of $f$, $\mathcal{O}_K$ its ring of integers, $\mathfrak{p}$ any prime of $\mathcal{O}_K$ lying over $p$ and $e$ its ramification index.

The hint/sketch: since $\overline{f}$ is irreducible, its splitting field $\kappa$ has degree $k$ over $\mathbb{F}_p$. We'd like to exhibit $\operatorname{Gal}(\kappa/\mathbb{F}_p)$ as a subquotient of the Galois group $\operatorname{Gal}(K/\mathbb{Q})$ via a map from the decomposition group $D(\mathfrak p)$, so then $k\mid |\operatorname{Gal}(K/\mathbb{Q})|=[K:F]$. The trouble is that $f$ is not monic, so it may not have roots in $\mathcal{O}_K$ (or even in the localization $(\mathcal{O}_K)_\mathfrak{p}$), and so it's not immediate that the factorization of $f$ in $K$ gives rise to a factorization of $\overline{f}$ in $\mathcal{O}_K/\mathfrak{p}$. The idea will be to use Vieta's formulas and an extension of the $p$-adic valuation to show that there are exactly $k$ roots of $f$ giving rise to the roots of $\overline{f}$ (namely, roots of $f$ with denominators not in $\mathfrak{p}$).

The solution: we shift attention to the localization $(\mathcal{O}_K)_{\mathfrak{p}}$, and let $\nu:=\nu_{\mathfrak p}$ be the $\mathfrak{p}$-adic valuation, so $\nu(x)=e\nu_p(x)$ for $x\in \mathbb{Q}$. Write $$f(x)=\sum_{i=0}^na_ix^i.$$
Then the hypotheses imply: (1) $\nu(a_i)>0$ for $i>k$; (2) $\nu(a_k)=0$; (3) $\nu(a_0)=0$. Here (1) and (2) are immediate and (3) follows by noting that $\overline{f}$ has no constant term otherwise, which would imply $\overline{f}$ has a root $x=0$ over $\mathbb{F}_p$ (so it is either reducible or has degree $1$). Let $r_i=c_i/d_i$, $1\leq i\leq n$ be the roots of $f$ in $K$, with $c_i,d_i\in (\mathcal{O}_K)_{\mathfrak{p}}$ not both in $\mathfrak{p}$. Let $R=\{r_1,\ldots,r_n\}$. For $0\leq \ell \leq n-1$, Vieta's formulas can be written
$$
a_\ell = (-1)^{n-\ell}\cdot a_n\cdot \sum_{\sigma\subset R\atop |\sigma|=n-\ell}\prod_{r_i\in \sigma}r_i.
$$
Furthermore, we have $a_n=\prod_{i=1}^nd_i$. In particular, $a_0=\prod_{i=1}^nd_i\cdot \prod_{i=1}^nr_i$ is the product of the numerators $c_i$, and (3) above then gives $\nu(c_i)=0$ for all $i$, so $\nu(r_i)=-\nu(d_i)$. Writing this out for $a_k$ and applying $\nu$ gives
$$
0=\nu(a_k) = \nu(a_n)+\nu\left(\sum_{\sigma\subset R\atop |\sigma|=n-k}\prod_{r_i\in \sigma}r_i\right).
$$
Recall the Strong Triangle Inequality: $\nu(\sum_{finite} x_i)\geq \min_i(\nu(x_i))$ with equality unless $\min_i(\nu(x_i))=\nu(x_i)=\nu(x_j)$ for some $i\neq j$.
Applied above, this gives
$$
0=\nu(a_n)+\nu\left(\sum_{\sigma\subset R\atop |\sigma|=n-k}\prod_{r_i\in \sigma}r_i\right)\geq \nu(a_n)+\min_{\sigma\subset R\atop |\sigma|=n-k}\left(\sum_{r_i\in \sigma}\nu(r_i)\right).
$$
Rearranging and applying $\nu(r_i)=-\nu(d_i)$ gives
$$
\nu(a_n)\leq-\min_{\sigma\subset R\atop |\sigma|=n-k}\left(\sum_{r_i\in \sigma}-\nu(d_i)\right)=\max_{\sigma\subset R\atop |\sigma|=n-k}\left(\sum_{r_i\in \sigma}\nu(d_i)\right).
$$
But $\nu(a_n)=\sum_{i=1}^n\nu(d_i)$, so we have
$$\sum_{i=1}^n\nu(d_i)\leq\max_{\sigma\subset R\atop |\sigma|=n-k}\left(\sum_{r_i\in \sigma}\nu(d_i)\right),$$
and we see that there can be at most $n-k$ values of $i$ for which $\nu(d_i)>0$, otherwise the left hand side will be larger than the right.

Now we claim that there are exactly $n-k$ values of $i$ for which $\nu(d_i)>0$. Suppose otherwise, so that there are exactly $\ell>k$ values of $i$ with $\nu(d_i)=0$. Then observe that, in the formula
$$
\nu(a_\ell) = \nu(a_n)+\nu\left(\sum_{\sigma\subset R\atop |\sigma|=n-\ell}\prod_{r_i\in \sigma}r_i\right)
$$
there is a unique term in the sum on the right with minimal valuation, namely $\prod_{r_i:\nu(r_i)\neq 0}r_i$, so the strong triangle inequality will give an equality, and we have
$$
\nu(a_\ell) = \nu(a_n)+\min_{\sigma\subset R\atop |\sigma|=n-\ell}\left(\sum_{r_i\in \sigma}\nu(r_i)\right)=\nu(a_n)+\min_{\sigma\subset R\atop |\sigma|=n-\ell}\left(\sum_{r_i\in \sigma}-\nu(d_i)\right)=\nu(a_n)-\max_{\sigma\subset R\atop |\sigma|=n-\ell}\left(\sum_{r_i\in \sigma}\nu(d_i)\right)=\sum_{r_i:\nu(r_i)\neq 0}\nu(d_i)-\sum_{r_i:\nu(r_i)\neq 0}\nu(d_i)=0
$$
contradicting (1) above, since $\ell>k$. Thus there are exactly $n-k$ values of $i$ with $\nu(d_i)>0$, and so after reindexing the roots $r_i$, we can write the (non-monic) factorization of $f$ over $(\mathcal{O}_K)_{\mathfrak{p}}$ as
$$
f(x)=\prod_{i=1}^{k}(x-c_i)\cdot \prod_{i=k+1}^{n}(d_ix-c_i).
$$
Let $g(x):=\prod_{i=1}^{k}(x-c_i)\in (\mathcal{O}_K)_{\mathfrak{p}}[x]$, and $\overline{g}$ its image in $((\mathcal{O}_K)_{\mathfrak{p}}/\mathfrak{p})[x]$. Notice that $\overline{f}(x)=\prod_{i=k+1}^nc_i\cdot \overline{g}(x)$. In particular, $\overline{f}$ splits over $(\mathcal{O}_K)_{\mathfrak{p}}/\mathfrak{p}$!

Now we're in the home stretch: $(\mathcal{O}_K)_{\mathfrak{p}}/\mathfrak{p}$ contains the splitting field $\kappa$ of $\overline{f}$, so letting $I(\mathfrak p)$ denote the inertia group at $\mathfrak{p}$ we conclude via $$k=[\kappa:\mathbb{F}_p]\mid [((\mathcal{O}_K)_{\mathfrak{p}}/\mathfrak{p}):\kappa][\kappa:\mathbb{F}_p]=[((\mathcal{O}_K)_{\mathfrak{p}}/\mathfrak{p}):\mathbb{F}_p]=\#\operatorname{Gal}(((\mathcal{O}_K)_{\mathfrak{p}}/\mathfrak{p})/\mathbb{F}_p)=\#D(\mathfrak{p})/\#I(\mathfrak{p})\mid \#D(\mathfrak{p})\mid \#\operatorname{Gal}(K/\mathbb{Q})=[K:\mathbb{Q}].$$


问:
intersection of dense sequence with compact subsets
Let $\{x_k\}$ be a dense sequence in $\mathbb R^2$ and let $E$ be a a non-singleton compact connected subset of $\mathbb R^2$. Is $\{x_k\}\cap E$  a dense sequence of $E$?

答: For a counterexample put $\{x_k\}=\Bbb Q^2$ and $E=[0,1]\times\{\sqrt{2}\}$.


问:
How did the approximation $\left(1+\frac{h}{R}\right)^{-2} \approx 1-\frac{2h}{R}$ come about?
In physics there is a formula calculate the variation in the acceleration due to gravity at a height, it is given by:

$$g=g_0\left(1+\frac{h}{R}\right)^{-2}$$

But it is approximated as $$g=g_0\left(1-\frac{2h}{R}\right)$$

Some how the terms in the brackets are almost equal could anyone show why ?

答:
Reacall binomial expansion for negative index as
$$(1+x)^{-2}=1-2x+\frac{-2(-3)}{2!}x^2+\frac{-2(-3)(-4)}{3!}x^3+...$$
When $x<<1$, then by retaining first two terms we wet the approximation:
$$(1+x)^{-2}\approx 1-2x.$$


问:
General interpretation of 'either...or'
I am studying the book 'How to Prove It: A Structured Approach by Daniel J. Velleman'

Now according to the textbook:

In mathematics, or always means inclusive or, unless specified otherwise, so we will interpret ∨ as inclusive or.

That means that we have a general interpretation of 'or'. My question is do we have a general interpretation of 'either...or' as well? If yes, then what is it?

In the book 'either...or' is interpreted as inclusive or. For example the statement

Either John went to the store, or we’re out of eggs.

is interpreted as

If we let $P$ stand for the statement “John went to the store” and $Q$ stand for
“We’re out of eggs,” then this statement could be represented symbolically
as $P \lor Q$.

I found this on Wikipedia  (go to 'Exclusive "or" in natural language'), which may be useful.

答: In mathematical writing, "either...or" is used with the same meaning as "or", namely it is inclusive.  The word "either" is just used to make the English flow naturally, and does not have any mathematical content.</p>

Title: General interpretation of 'either...or'


问:
EXERCISE 1.2.ii (ii) of "CATEGORY THEORY IN CONTEXT"
How to solve the EXERCISE 1.2.ii (ii) of Riehl's "CATEGORY THEORY IN CONTEXT"?

EXERCISE 1.2.ii (ii) is the following.

A morphism $f: x \to y$ is a split epimorphism in a category $C$ if and only if for all $c \in C$, post-composition $f_{*}: C(c, x) \to C(c, y)$ defines a surjective function.
Argue by duality that $f$ is a split monomorphism if and only if for all $c \in C$, pre-composition $f^{*}: C(y, c) \to C(x, c)$ is a surjective function.

Now I can show that a morphism $f: x \to y$ is a split epimorphism in a category $C$ if and only if for all $c \in C$, post-composition $f_{*}: C(c, x) \to C(c, y)$ defines a surjective function.

And without the arguement by duality I can show that $f$ is a split monomorphism if and only if for all $c \in C$, pre-composition $f^{*}: C(y, c) \to C(x, c)$ is a surjective function.

But I cannot show the above statement using the arguement by duality.

答:
Suppose that the following statement in $C^{op}$ holds. The statement in $C^{op}$ is equivalent to the statement in $C$. Therefore the statement in $C$ holds.

statement in $C^{op}$

$f^{op}: x \to y$ is a split epimorphism in $C^{op}$ if and only if for all $c \in C^{op}$, post-composition $f_{*}: C^{op}(c, x) \to C^{op}(c, y)$ defines a surjective function.

statement in $C$

$f: y \to x$ is a split monomorphism in $C$ if and only if for all $c \in C$, pre-composition $f^{*}: C(x, c) \to C(y, c)$ defines a surjective function.


问:
Why does a cumulative distribution have the quality that $P(X<b)=\lim_{n\to\infty}\left[P\left(X\leqslant b-\frac1n\right)\right]$?
I came across the following passage in Ross' "First Course in Probability":

If we want to compute the probability that X is strictly less than b , we can apply the continuity property to obtain:
$$P\bigl(X<b\bigr)=\lim_{n\to\infty}\left[P\left(X\leqslant b-\frac1n\right)\right].$$

The continuity Ross is referring to, is the right continuity of the cumulative function but the property he mentions seems to me to be a property of a left continuity since the sequence $b-\dfrac1n$, where $n$ goes to infinity, is an increasing sequence that converges to $b$ from left to right.
Will be grateful for any enlightening remarks on this.

答:
The continuity Ross is referring to, is the right continuity of the cumulative function...

Not quite. Ross is referring to "probability as a continuous set function", which he states as a proposition as "If $\{E_n, n \ge 1\}$ is either an increasing or decreasing sequence of events, then

$$\lim_{n \to \infty}P(E_n) = P\left(\lim_{n \to \infty} E_n\right)$$

" In the ninth edition this is stated and proven in section 6 of chapter 2.

Left continuity of the cdf would say

$$\lim_{n\to\infty} P\left(X \le b - \frac{1}{n}\right)= \lim_{n\to\infty} F\left(b - \frac{1}{n}\right) =   F\left(\lim_{n\to\infty} b - \frac{1}{n}\right)  = F(b) = P(X \le b)$$

which Ross does not claim.


问:
problem on matrix derivatives
If I have two $3\times3$ rotation matrices $R_1$ and $R_2$, what is the matrix derivatives of $\frac{\partial(R_1 R_2^T)}{\partial R_1}$?

Also, I have found a website which can answer my question

http://www.matrixcalculus.org/
The following is the answer:

I am not sure whether this is the correct answer? Also,I don't understand the meaning of the notation ∏. Can someone explain it for me？Thanks

答: I think (not sure about this one) that it is saying the Kronecker Product of $R2^T$ and a generalized Identity Matrix. I say this because the symbol after $\otimes$ is $\mathbb{I}$ (not $\Pi$), or $\mathbb{I}$

Title: problem on matrix derivatives


答:
I suppose this is not inherently different from the other answers posted, but you can get this from the simple Taylor expansion:
$$
f(x) \approx f(0) + x f'(0),\qquad\text{where}\qquad f(x)= (1 + x)^{-2}.
$$
This gives $f(x) \approx 1 - 2x$ or, with $x = h/R$,
$$
\left(1 + \frac h R\right)^{-2}
\approx
1 - \frac{2h}{R}.
$$
By Taylor's theorem with remainder, the error is at most $3h^2 / R^2$ (i.e., the quadratic term in the series expressions give by other users).


答:
Jacobi invert always invert. I am going to find the probability of not finding any consecutive cards then I will do 1-p.

1st draw. it doesn't matter, for practical purpouses let's say you draw a 1

2nd draw. you have to draw either a 1, 3, 4 or 5 (q=23/35).

3rd draw.

if 2nd was 1 -> you have to draw either a 1, 3, 4 or 5 (r=22/34) => $22/34*5/35$

if 2nd was 3 -> you have to draw either a 1, 3 or 5 (r=16/34) => $16/34*6/35$

if 2nd was 4 -> you have to draw either a 1 or 4 (r=10/34) => $10/34*6/35$

if 2nd was 5 -> you have to draw either a 1, 3 or 5 (r=16/34) => $16/34*6/35$

Then your probability is $1-22/34*5/35-16/34*6/35-10/34*6/35-16/34*6/35=414/595$

Title: Probability of Consecutive Cards

Body:
I've got a deck of 36 cards... 6 are labeled with #1, 6 with #2, and so on up to 6 with #6. I'm drawing 3 cards from the deck & wondering what the probability is that I will end up with 2 or more consecutive cards (including wrap-arounds--meaning a #6 can wrap-around to a #1 and visa-versa).

I know that it's 66.7% WITH replacement as I actually drew the whole thing out on a spreadsheet with every possible outcome (and got 24/36), but I know that the number will increase WITHOUT replacement, and I'm just not sure how to come up with the formula to figure it out.

I came up with this formula... 12/35 + (24/35 x 12/34)+(16/35 x 12/34) = 74.6%, but that seems way too high as I can't see an 8% jump just because I didn't replace 2 cards.

Is there anybody out there who can help me?


问:
connecting regression to the formal definition of a statistical model
I would like to know how regression model is a statistical model. The formal definition of a statistical model according to wikipedia is as follows:

a statistical model is usually thought of as a pair ( S, P) where
where S is the set of possible observations, i.e. the sample space,
and P is a set of probability distributions on S.

How does Regression model normally written as below map to the above formal definition of a statistical model?
$y_{i}=\beta _{1}x_{i1}+\beta _{2}x_{i2}+\cdots +\beta _{p}x_{ip}+\varepsilon _{i},\, $

答:
After a long process, I finally can provide my answer.I accepted @angryavian's response but I also am adding the extra points I learned and are relevant to a fuller answer.
In linear regression for each observation yi, we assume =11+22+⋯++. Assuming Y to be a vector of all y_i and X (design matrix $n \times p$) to be deterministic, and $\varepsilon ~ \mathscr N(0, \sigma^2  I_n)$ then $Y= XB+ \varepsilon$  therefore, given that $\varepsilon$ is a gaussian and $XB$ is deterministic for any given $B$ therefore $XB+ \varepsilon$ is $ \mathscr N_n(XB, \sigma^2I_n)\}$ and our model is  probability distribution family $ \{ \mathscr N_n(XB, \sigma^2I_n)\}_B \in \mathbb R^p$


问:
Infinite Series question

The first one, the effective resistance is $2R$, then $5R/3$ then $13R/8$ etc....
My job is to find the pattern/equation so I can find the total resistance when $20$ resistors are connected. Of course I can do the long way by using this formula I created
$R_n = (R_{n-1} \times R)/(R_{n-1} +R) +R$. Can you guys help me find an equation where I can just input the value of $n$ and simply get an answer. Thanks!

The second question is: What would I get if I had an infinite number of resistance.

Help is very much appreciated :)

答:
Let $R_n$ be the resistance of a circuit with $2n$ resistors, so $R_1 = 2R$.  The circuit with $2(n+1)$ resistors is obtained from the circuit with $2n$ resistors by placing one resistor in parallel and another one in series.  So

$$
R_{n+1} = R + \frac{1}{\frac{1}{R} + \frac{1}{R_n}} = R + \frac{R R_n}{R+R_n}.
$$

Substituting $R_n = \frac{p_n}{q_n}R$ gives

$$
R_{n+1} = R + \frac{R R_n}{R+R_n} = \frac{2p_n + q_n}{p_n + q_n}R
$$

and so we can take $p_{n+1} = 2p_n + q_n$ and $q_{n+1} = p_n+q_n$.  Placing these numbers in a sequence like

$$
q_1, p_1, q_2, p_2, q_3, p_3, \dotsc
$$

results in the Fibonacci sequence

$$1,2,3,5,8,13,\dotsc$$

for which explicit expressions can be found on the wp page (with a shifted index $n$).  In the limit the quotient $\frac{p_n}{q_n}$ of two consecutive Fibonacci numbers tends to the golden ratio $\varphi = \frac{1+\sqrt{5}}{2}$.

Title: Infinite Series question


问:
linearizing non-strict inequality If.. else conditional constraint that includes decision variables
I would like to linearize a conditional constraint as follow:

0 <= x1 <= 1.

If 0 <= x1 < 1, then x2 = 1, else x2 = 0.

I find it very difficult because it is not a typical If...then constraint. Any suggestions or answers are greatly appreciated. Thanks!

JZ

答:
Let $\epsilon>0$ be a small constant.  You can linearize the relationship as follows:
$$1-x_2 \le x_1 \le 1-\epsilon x_2$$

Just check the two cases for $x_2 \in\{0,1\}$.

More generally, if you want to enforce $x_1 \in [a,b] \cup [c,d]$, you can use
$$a x_2 + c (1-x_2) \le x_1 \le b x_2 + d (1-x_2).$$
Your problem corresponds to $(a,b,c,d)=(0,1-\epsilon,1,1)$.

Even more generally, see Decision variable must lie in union of multiple disjoint intervals.


问:
How many $k$-letter words are there such that the letters A and B are not next to each other?
I spent the better part of a long car ride today thinking about the following problem:

Consider an alphabet of $n$ letters. How many $k$-letter words of this alphabet are there such that two certain letters (say A and B) are not next to each other? A word may contain the same letter multiple times.

My thoughts: There are $n^k$ words with length $k$ over the alphabet. We need to find and subtract away the number of words where A and B are next to each other. I modeled any such word as one with the string AB or BA at an index $i$:

$$x_1x_2x_3\cdots x_{i-1}ABx_{i+2}\cdots x_k$$

The $x_j$ here are all letters of the alphabet. We can think of the above word as an $(i-1)$-letter word, followed by AB, followed by a $(k-i-2)$-letter word. Thus, there are $n^i \cdot n^{k-i-2} = n^{k-2}$ words where AB or BA is at an arbitrary index $i$. Summing over all $i$, we get that there are $(k-2)n^{k-2}$ words containing AB and $2(k-2)n^{k-2}$ words containing AB or BA. Our final expression for the number of $k$-letter words such that A and B are not adjacent is

$$n^k - 2(k-2)n^{k-2}$$

There’s an issue though. I’m over-counting words that contain AB or BA by a lot. I ran a simulation, and at $n=k=10$, for example, the correct value is $8441614754$, and my answer is $8400000000$. By this method, any word that contains AB or BA more than once is counted more than once. Is there any way I can modify this approach to yield the correct result? If not, how should I proceed?

答:
Consider the following automaton that accepts the strings not containing AB or BA,

From the DFA, using Chomsky-Schutzemberger method, we get,
$$q_0 = 1+xq_1+xq_2+(n-2)xq_0$$
$$q_1 = 1+xq_1+(n-2)xq_0$$
$$q_2 = 1+xq_2+(n-2)xq_0$$
(We omit $q_3$ and $q_4$ because it is a dead state)

On solving the above equations (i.e. substituting $q_1$ and $q_2$) we get the following expression for $q_0$,
$$q_0 = \frac{1+x}{1-(n-1)x-(n-2)x^{2}}$$
This is our generating function. The coefficient of $x^{k}$ gives the number of strings of length k not having AB or BA.
For example, for $n = k = 10$, Wolfram Alpha gives the following Taylor Series,

And as you can see, the coefficient of $x^{10}$ is equal to the answer you have provided.