答:
In the argument above $y$ is fixed, and $\|y\|<\frac{r}{2}$. So say
$\|y\|=\frac{r-\varepsilon}{2}$.

Then $F(x)=y-g(x)$ maps $\overline{B(0,r-\varepsilon)}$ into itself, since
$$
\|F(x)\|\le \|y\|+\|g(x)-g(0)\|\le \frac{r-\varepsilon}{2}+\frac{1}{2}\|x-0\|\le r-\varepsilon.
$$

Title: Tao Analysis 2 Lemma 6.6.6 (lemma for inverse function theorem)

Body:
Let $B(0,r)$ be a ball in $\mathbb{R}^n$ centered at the origin, and let $g: B(0,r) \to \mathbb{R}^n$ be a map such that $g(0) = 0$ and
$$||g(x) - g(y)|| \le \frac12 ||x-y||$$
for all $x,y \in B(0,r)$ (here $||x||$ denotes the length of $x$ in $\mathbb{R}^n$). Then, the functions $f : B(0,r) \to \mathbb{R}^n$ defined by $f(x) : = x + g(x)$ is one to one, and furthermore the image $f(B(0,r))$ of this map contains ball $B(0,r/2)$.

I understand how to prove one to one. The proof for the second part is on the picture below.

It is not clear to me how the same argument shows that $F$ maps $\overline{B(0, r-\epsilon)}$ to itself. If I use the same argument when $x \in \overline{B(0, r-\epsilon)}$,
$$||F(x)|| \le ||y|| + ||g(x)|| \le \frac{r}2 + ||g(x) - g(0)|| \le \frac{r}2 + \frac{r-\epsilon}2 = r- \frac{\epsilon}2$$
This is not sufficient to show that it maps to $\overline{B(0, r-\epsilon)}$. I think I am missing something here. I would appreciate if you give some help.


问:
Can we treat a Hasse diagram as a simple undirected graph?
Simple undirected graph. A graph is simple if there is no self-loops and multiple edges,  and undirected if the edges are undirected.

Hasse diagram.
In a Hasse diagram, the edges $u\rightarrow v$ are drawn in the plane such the vertex $u$ is placed below the vertex $v$ and there is an undirected edge $u-v$. By doing so, we can drop the direction in a Hasse diagram.

Can we treat a Hasse diagram as a simple undirected graph in graph theory or computer science?

答: The most general answer would be "it depends". Hasse diagrams do have vertices and edges, so technically they may be seen as graphs. However, if we wish to analyze the relations through these graphs, this could pose some problems. Firstly, if we had edges $u-v$ and $v-w$ in the Hasse diagram of a relation $\sim$, this means that due to transitivity of the relation we have $u \sim w$ - however, this relationship is not explicitly depicted in the Hasse diagram. Secondly, if we treat the Hasse diagram as an undirected graph, we lose the information resulting from the orientation of the Hasse diagram - it happens because graphs do not have orientation. If we flipped it upside down, it would not change the graph. However, we cannot flip the Hasse diagram upside down, as we would get a Hasse diagram of a completely different relation.

ContentLicense: CC BY-SA 4.0


问:
Converting units of standard deviation
celsius=5/9(fahrenheit− 32)

if the standard deviation of a random sample containing 14 people is 0.9 degrees farenheit, what's the variance in celsius?

I have tried 5/9(0.18-32) but I get a negative number for variance which is obviously wrong. I used 0.18 because 0.9^2=0.18.

答:
Shifting the data does not change the deviations at all. So the subtraction is completely irrelevant to this problem.

Multiplying the data by $\frac59$ multiplies the standard deviation by $\frac59$.

Once you know the standard deviation in Celsius, it's not difficult to find the variance.

Title: Converting units of standard deviation


问:
$\sum\limits_p\log\left(\frac{1}{1-\frac{1}{p^s}}\right)=\sum\limits_p \sum\limits_{n\geq 1}\frac{1}{np^{ns}}$
I am not seeing the second equality (after Euler's product) of this equality of the Riemann $\zeta$-function for $\operatorname{Re}(s)>1$
$$\log(\zeta(s))=\sum\limits_p\log\left(\frac{1}{1-\frac{1}{p^s}}\right)=\sum\limits_p \sum\limits_{n\geq 1}\frac{1}{np^{ns}}$$
where $p$ means summation over all primes.
I tried writing the logarithm as Maclaurin series but this gives me a minus sign in front of the inner sum: Let $q:=\frac{1}{1-\frac{1}{p^s}}$ then
$$\sum\limits_p\log\left(1-1+ q\right)=\sum\limits_p \left(-\sum\limits_{n\geq 1}\frac{1}{n}(1+q)^n\right)$$
If I use the identity for $\log(1+(q-1))$ I have this alternating $(-1)$ term in front. I also tried to write the $q$ as a geometric series but then I don't see how I can eliminate the logarithm:
$$\sum\limits_p\log\left(\frac{1}{1-\frac{1}{p^s}}\right)=\sum\limits_p\log\left(\sum\limits_{n\geq 1}(p^{-s})^n\right)$$

答:
\begin{eqnarray*}
\log\left(\frac{1}{1-\frac{1}{p^s}}\right)=- \log \left(1-\frac{1}{p^s} \right).
\end{eqnarray*}
Now expand using
\begin{eqnarray*}
- \log (1-u) = \sum_{n=1}^{\infty} \frac{u^n}{n}.
\end{eqnarray*}


问:
Generating functions for combinatorics
I have no formal education in generating functions, but, based on another question, I have seen that they can be powerful for combinatorics.

Are there a few general principles for using generating functions to construct counting arguments (e.g. counting the number of subsets or number of total orderings) that can be remixed to count different quantities?

If the answer is not amenable to this forum, where can I learn more?

I've been trying to read Concrete Mathematics (Graham, Knuth, Patashnik), but the topic spans several chapters and over 100 pages. At the moment, I just have patience to learn the gist of the combinatorics applications of generating functions. Maybe later I'll go back and get an extensive education from GKP.

答: I'd also recommend Wilf's Generatingfunctionology. It is available online.  If you like it, do Wilf the courtesy of buying a copy.</p>

ContentLicense: CC BY-SA 3.0

Title: Generating functions for combinatorics


问:
Trigonometry Addition Thereom With Only one exact value?
Use the expression of $\sin(A+B)$ to evaluate $\sin 195$.

Do I use one exact value like $45+150$ or $60$ or is there another way?

答: Here you go: $\sin 195° = -\sin 15° = -\sin(45-30)°$. After that you use standard formulas.</p>


问:
Sketch of proof concerning a conjecture of Vasile Cirtoaje : $(1-x)^{(2x)^k}+x^{(2(1-x))^k}\leq 1$ with $k\geq1$ and $0<x\leq \frac{1}{2}$

Claim

Prove that [1]:

Let $0<x\leq 0.5$ and $k\geq 1$ a real number then we have :

$$h(k)=(1-x)^{(2x)^k}+x^{(2(1-x))^k}\leq 1$$

Sketch of proof :

The case $k\geq 1+\alpha$ :

We define $\alpha$ as :

$$\lim_{x\to 0.5^-}=\frac{\ln\Big(2(2^{2x}x^2(1-x)2)\Big)}{\ln(2x)}=\frac{\ln\Big(2(1-(2^{2x}x^2(1-x)2))\Big)}{\ln(2(1-x))}=\alpha=1.69315\cdots$$

We have :

$$x^{2(1-x)}\leq2^{2x}(1-x)2x^2$$

And :

$$(1-x)^{2x}\leq 1-2^{2x}(1-x)2x^2$$

For a sketch of proof see Refinements of the inequality $f(x)=x^{2(1-x)}+(1-x)^{2x}\leq 1$ for $0<x<0.5$

So we have :

$$x^{(2(1-x))^k}\leq f(x)^{(2(1-x))^{k-1}}=(2^{2x}(1-x)2x^2)^{(2(1-x))^{k-1}}$$

And :

$$(1-x)^{(2x)^k}\leq (1-2^{2x}(1-x)2x^2)^{(2x)^{k-1}}$$

Now we want $y\geq 1$ a real number :

$$(2x)^{k-1}\geq (2f(x))^{y}$$
And
$$(2(1-x))^{k-1}\geq (2(1-f(x)))^{y}$$

Solving this we have

$$\frac{\ln\Big(2(1-(2^{2x}x^2(1-x)2))\Big)}{\ln(2(1-x))}\leq \frac{k-1}{y}\leq \frac{\ln\Big(2(2^{2x}x^2(1-x)2)\Big)}{\ln(2x)}\quad (1)$$

The constraint $(1)$ is honoured if :$$\alpha=\frac{k-1}{y}$$

So we have :

$$x^{(2(1-x))^k}\leq (f(x))^{(2(1-f(x))^{\frac{k-1}{\alpha}} }\quad (2)$$

And :

$$(1-x)^{(2x)^k}\leq (1-f(x))^{(2f(x))^{\frac{k-1}{\alpha}}}\quad (3)$$

Adding $(2)$ and $(3)$ we have :

$$h(k)\leq (1-f(x))^{(2f(x))^{\frac{k-1}{\alpha}}}+(f(x))^{(2(1-f(x))^{\frac{k-1}{\alpha}}}$$

We can repeat the reasoning $p$ times ($p\geq 1$ a natural number) and the last exponent becomes :

$$1\leq \frac{k-1}{\alpha^p}\leq \alpha$$

It's true because we can always choose $k$ such that :

$$\alpha^p\leq k \leq \alpha^{p+1}$$

So we reduce this case to the case $1\leq k\leq 1+\alpha $

Case $k\leq 1+\alpha $

Using Bernoulli's inequality and derivatives we have $1\leq k\leq 2$ and $0<x\leq \frac{1}{4}$

$$(1-x)^{(2x)^k}\leq 1-x(2x)^k$$
And
$$x^{(2(1-x))^k}\leq x(2x)^k$$

In the same idea we have $2\leq k\leq 1+\alpha$ and $0<x\leq \frac{1}{3}$

$$(1-x)^{(2x)^k}\leq 1-x(2x)^k$$
And
$$x^{(2(1-x))^k}\leq x(2x)^k$$

Now  to finalize the sketch of proof we have :

$h(k)$ is decreasing for $1\leq k\leq 2$ and $ \frac{1}{4}\leq x\leq 0.5\quad (4)$

$h(k)$ is decreasing for $2\leq k\leq 1+\alpha$ and $ \frac{1}{3}\leq x\leq 0.5\quad (5)$

Questions :

It is good and coherent ?

How to show $(4)$ and $(5)$?

Thanks in advance !

Regards Max

[1] Vasile Cirtoaje, "Proofs of three open inequalities with power-exponential functions",
The Journal of Nonlinear Sciences and its Applications (2011), Volume: 4, Issue: 2, page 130-137.
https://eudml.org/doc/223938

https://link.springer.com/article/10.1186/1029-242X-2013-468

答:
I have a second sketch/Partial  proof (tell me if i'm wrong) :

We want to show

Let $0.65\leq x<1$ and $1\leq k\leq n$ two naturals numbers with $n\geq 10^{10}$ then we have ::

$$P(k)=(1-x)^{(2x)^{1+\frac{k}{n}}}+x^{(2(1-x))^{1+\frac{k}{n}}}\leq 1\quad (I)$$

We use a form of the Young's inequality or weighted Am-Gm :

Let $a,b>0$ and $0<v<1$ then we have :

$$av+b(1-v)\geq a^vb^{1-v}$$

Taking account of this theorem and putting :

$a=(x)^{(2(1-x))^{1+\frac{k}{n}}}$$\quad$$b=1$$\quad$$v=(2(1-x))^{\frac{1}{n}}$ we get :

$$(x)^{(2(1-x))^{1+\frac{k}{n}}}\leq (x)^{(2(1-x))^{1+\frac{k-1}{n}}}(2(1-x))^{\frac{1}{n}}+1-(2(1-x))^{\frac{1}{n}}$$

Now the idea is to show :

Let $$(1-x)^{(2x)^{1+\frac{k}{n}}}\leq 1-\Big((x)^{(2(1-x))^{1+\frac{k-1}{n}}}(2(1-x))^{\frac{1}{n}}+1-(2(1-x))^{\frac{1}{n}}\Big)$$

Or:
$$(1-x)^{(2x)^{1+\frac{k}{n}}-\frac{1}{n}}+2^{\frac{1}{n}}(x)^{(2(1-x))^{1+\frac{k-1}{n}}}\leq 2^{\frac{1}{n}}\quad (0)$$

Now we have $x\in[0.65,1)$ :

$$2^{\frac{1}{n}}(1-x)^{(2(1-x))^{1+\frac{k-1}{n}}}\geq (1-x)^{(2(x))^{1+\frac{k}{n}}-\frac{1}{n}}\quad(1)$$

Putting $(1)$ into $(0)$ we can use a proof by induction and conlude with Refinements of the inequality $f(x)=x^{2(1-x)}+(1-x)^{2x}\leq 1$ for $0<x<0.5$

Edit :

Now I can complete it :

The problem can be considered as :

$$r(x)=\left((1-x)^{-\left(2\left(x\right)\right)^{k}}-1\right)\left((x)^{-\left(2\left(1-x\right)\right)^{k}}-1\right)\geq1$$

Lemma

Let $1< x$ and $a>2$ then we have :

$$f(x)=\left(1+\frac{\left(\ln\left(ax\right)^{c}-\ln\left(a\right)^{c}\right)}{\left(\ln\left(2a\right)^{c}-\ln\left(a\right)^{c}\right)}-x\right)\leq 0$$

We can find $c$ as $f'(2)=0$.The definition of $c$ involves the Lambert's function.

Proof :

We have :

$$f'(x)=\frac{c(\ln(ax))^{c-1}}{x\left(\ln\left(2a\right)^{c}-\ln\left(a\right)^{c}\right)}-1$$

We substitute $x=\frac{1}{y^{c-1}a}$

The inequality have the form :

$$\ln(u)u=p$$

Wich is just the Lambert's function . The rest is easy .

End of the proof .

Now we apply twice the second lemma and we start by introducing (see the reference) :

$$f(x)=((\ln((a)b^{-(2(1-b))^x}))^c-(\ln(a))^c) ((\ln((a)(1-b)^{-(2(b))^x}))^c-(\ln(a))^c)$$

The derivative is :

$$f'(x)=c(u(x)+v(x))$$

Where :

$$u(x)=\left(2-2b\right)^{x}\cdot\ln(2\left(1-b)\right)\cdot\ln(b)\cdot\left((\ln(a))^{c}-\left(\ln(a\cdot\left(1-b\right)^{-(2b)^{x}})\right)^{c}\right)\left(\ln(a\cdot(b)^{-\left(2-2b\right)^{x}})\right)^{\left(c-1\right)}$$

$$v(x)=2^{x}\cdot b^{x}\cdot\ln(1-b)\cdot\ln(2b)\cdot\left((\ln(a))^{c}-\left(\ln(a\cdot b^{-(2-2b)^{x}})\right)^{c}\right)\left(\ln(a\cdot(1-b)^{-2^{x}b^{x}})\right)^{\left(c-1\right)}$$

A bit of Algebra and we need to show something like:

$$\frac{\left(2-2b\right)^{x}\cdot\ln(2\left(1-b)\right)\cdot\ln(b)}{2^{x}\cdot b^{x}\cdot\ln(1-b)\cdot\ln(2b)}\geq^{?}-\left(\frac{\left((\ln(a))^{c}-\left(\ln(a\cdot\left(1-b\right)^{-(2b)^{x}})\right)^{c}\right)\left(\ln(a\cdot(b)^{-\left(2-2b\right)^{x}})\right)^{\left(c-1\right)}}{\left((\ln(a))^{c}-\left(\ln(a\cdot b^{-(2-2b)^{x}})\right)^{c}\right)\left(\ln(a\cdot(1-b)^{-2^{x}b^{x}})\right)^{\left(c-1\right)}}\right)^{-1}\quad(U)$$

We can split in two the problem as :

$$\left(\frac{\left((\ln(a))^{c}-\left(\ln(a\cdot\left(1-b\right)^{-(2b)^{x}})\right)^{c}\right)}{\left((\ln(a))^{c}-\left(\ln(a\cdot b^{-(2-2b)^{x}})\right)^{c}\right)}\right)^{-1}\geq^{?}\frac{\left(\left(2-2b\right)^{x}\right)^{\left(1+v\right)}\cdot\ln(b)}{\left(2^{x}\cdot b^{x}\right)^{\left(1+w\right)}\cdot\ln(1-b)}$$

And :

$$-\left(\frac{\left(\ln(a\cdot(b)^{-\left(2-2b\right)^{x}})\right)^{\left(c-1\right)}}{\left(\ln(a\cdot(1-b)^{-2^{x}b^{x}})\right)^{\left(c-1\right)}}\right)^{-1}\leq^{?}\frac{\left(\left(2-2b\right)^{x}\right)^{\left(-v\right)}\cdot\ln(2-2b)}{\left(2^{x}\cdot b^{x}\right)^{\left(-w\right)}\cdot\ln(2b)}$$

With $v,w>0$

It works for small values so it's perfect for $1\leq k\leq 3$ and $a$ sufficiently big and $0.5\leq x\leq0.75$ .

I pursue it later .

Vasile Cirtoaje, "Proofs of three open inequalities with power-exponential functions",

The Journal of Nonlinear Sciences and its Applications (2011), Volume: 4, Issue: 2, page 130-137.
https://eudml.org/doc/223938

Miyagi, M., Nishizawa, Y. Proof of an open inequality with double power-exponential functions. J Inequal Appl 2013,

https://link.springer.com/article/10.1186/1029-242X-2013-468


问:
Anagram consecutive letters probability
Say I have a word like resemblance with 11 letters and 3 e letters.
I know there are 11!/3!=6652800 anagrams for the word. (Not real words obviously.)

My question is what is the probability within those permutations that all three e letters are next to one another? Thanks.

答: Hint: treat the three adjacent "e"s as a single letter so that you effectively have 9 letters. This will allow you to count the number of words such that the three "e"s are together, and you can then divide by $11!/3!$ to obtain the probability.

Title: Anagram consecutive letters probability


问:
Curve fitting with an invertible function
I have some data that need to be transformed as shown in the picture given some function.

example of input data and desired result

The function in question can take whatever form but with the following requirements:

It needs to be able to fit the data shown (i.e f(orange data) = blue data as much as possible)

It needs to be invertible

I need to be able to adjust its parameters so that in certain conditions it becomes identity

I've played around with various functions and although I can find various options that give a perfect fit, either I can't invert them or I can't figure out how to adjust the parameters to get an identity.

To give a more concrete example, let's say that a function of the form f(x) = ax + b could work (it doesn't). In this case the inverse function would be finv(x) = (x-b)/a.
Now we could imagine a weight that is provided as an external parameter which goes between 0-1, in which case I could adjust parameters a and be so that

a'= w*a - (1-w) -> so that when the weight is at 1 we get the desired fitting behavior, when the weight is at 0 we get 1

b' = w*b -> so that b becomes 0 when the weight is 0
The above would give me f(x) = x when the weight is at 0 and ax+b when the weight is at 1.

What function could fulfil all 3 criteria given the form of the data I have?

Any ideas would be extremely welcome, I've been looking at this for days and I'm getting nowhere.

Thanks!

Edit to add some examples that give me a good fit:
f(x) = ax/(b-x)^c

good fit, I can get it to become identity, but I don't see how to invert
f(x) = (ax/(b-x))^c

good fit, invertible but can't get it to become identity

Throwing more parameters at it:
f(x) = (ax^b)/(c-x^d)

again good fit, identity if I set a=1, b=1, c=2, d=0 but can't see how to invert

答:
The subject of your question is so wide and under-defined that I may provide only some general considerations and hints.

a) Since you are considering invertible functions, then you shall treat both coordinates "equivalently", meaning that you shall use
Total regression, and in particular Deming regression.

b) To cope with invertibility requirement, you can probably use geometric regression,
i.e. to fit curves implicitly defined as $f(x,y)=c$, since in that case inversion would just be $f(y,x)=c$.

You can for instance start and consider the conics.

c) You will always have  two  translation parameters, two scale parameters ad one rotation parameter, besides that defining ellipse/ parabola/ hyperbola.


问:
Cutting a torus along a surface non-separating cycle
Is it true that if we cut a torus along a surface non-separating cycle then it will form a cylinder? It's clearly true for a simple surface non-separating cycle that is like a ring on a donut. But what about more complex surface non-separating cycles with larger winding numbers?</p>

答:
Yes, this follows from the classification of surfaces (with boundary) and an Euler characteristic calculation.

If S is the surface obtained after cutting then then note that we have expressed the torus as a connect sum $T = A \# S$ (by taking a small neighbourhood around the curve you cut along). T has Euler characteristic $0$ and anulus (= cylinder) has Euler characteristic, 0. Hence, by the formula for the Euler characteristic of a connect sum $S$ has Euler characteristic $0$. It also has 2 boundary components and is orientable. Now the result follows from the classification of orientable surfaces boundary, i.e. there is a unique orientable surface with 2 boundary components and Euler characteristic $0$: the anulus (= cylinder).


问:
Showing that a set of trigonometric functions is a basis of $V$
Once again I am asking for help, I'm preparing for my linear algebra exam by doing a practice exam. The problem goes as following.

Let $\beta$ be the subset $\{1,e^x\cos x,e^x\sin x\}$ of a vector space of infinite many differentiable real functions on $\mathbb{R}$. Let $V=\text{Span} \beta$ then $\beta$ is a basis for $V$. Now let $\mathcal{C}=\{1+e^x\cos x,1+e^x\sin x,e^x\left(\cos x+\sin x\right)\}$ I have to show that $\mathcal{C}$ is a basis for $V$. For it to be a basis of $V$ it has to span $V$ and be linearly independent. To show that $\mathcal{C}$ is linearly indepdent, let $a,b,c,d,e,f\in\mathbb{R}$ such that $x\mapsto a+be^x\cos x+c+de^x\sin x+e^x\left(e\cos x + f\sin x \right)$ is the $\theta(x)$ function, i.e the zero function. Meaning that we have to show $a=b=c=d=e=f=0$. Do I just test with different values, i.e letting $x=0,\pi,\frac{\pi}{2}...$. I'm not sure if this helps, but I noticed that if we denote the functions in $\beta$ as $\beta=\{f_1,f_2,f_3\}$ then $\mathcal{C}=\{g_1,g_2,g_3\}$ in other words $g_1=f_1+f_2, g_2=f_1+f_3, g_3=f_3+f_2$. I also tried differentiating it, I noticed that then $a=c=0$

答:
$a(1+e^x\cos x)+b(1+e^x\sin x)+c(e^x\left(\cos x+\sin x\right))=0$

$(a+b)+(a+c)e^x\cos x+(b+c)e^x\sin x=0$

we know that elements of $\{1,e^x\cos x,e^x\sin x\}$ are lienarly independent so

$c_1+c_2e^x\cos x+c_3e^x\sin x=0$ $\Rightarrow$ $c_1=c_2=c_3=0$ Hence

$a+b=a+c=b+c=0$ $\Rightarrow$ $a=b=c=0$ which means they are linearly independent

so C forms a basis


问:
Help making Lipschitz proof rigorous
A function $f:R→R$ is defined to be Lipschitz if there is a constant $K>0$ such that for all $a,b∈R$ $$|f(a)−f(b)|≤K|a−b|$$

Suppose $f:R→R$ is Lipschitz. Prove that $f$ is continuous.

Could someone please verify that my solution is completely rigorous? I think that there may be a slight problem with my proof since I used $|x-y|<δ$ and not $0<|x-y|<δ$. If this means that the proof is not rigorous, I would very much appreciate it if someone could fix the proof so that it is rigorous. Thanks in advance!

答:
let $ϵ>0$ and $x,y ∈R$

for $f$ to be continuous at $y$, need to ensure that $|f(x)−f(y)|<ϵ$

we are given $$|f(a)−f(b)|≤K|a−b|$$

now, whenever $|x-y|<δ$ we have: $$|f(x)−f(y)|<Kδ$$

let $δ = \frac{ϵ}{K}$

therefore we have: $$|f(x)−f(y)|<ϵ$$

therefore by choosing  $δ = \frac{ϵ}{K}$  we have ensured that whenever $|x-y|<δ$, we have $$|f(x)−f(y)|<ϵ$$

i.e. $f$ is continuous on all $y∈R$

i.e. $f$ is continuous over its domain.

Title: Help making Lipschitz proof rigorous


问:
Tree diagram Chain Rule
Let
$$
\begin{align}
w &= f(x,y,z)\\
z &= z(x,y)\\
x &= x(t)\\
y &= y(t)\\
\end{align}
$$
be differentiable functions.

Find the formula for the derivative of $w$ with respect to $t$.

My answer:
$w = f(x,y,z) \implies \dfrac{dw}{dt} = \dfrac{dw}{dx} \cdot \dfrac{dw}{dy} \cdot\dfrac{dw}{dz}$
$$
\begin{align}
z &= z(x,y) \\
x &= x(t) \\
y &= y(t) \\
\end{align}
\implies \frac{dz}{dt} = \frac{\partial z}{\partial x} \cdot \frac{dx}{dt} + \frac{\partial z}{\partial y}\cdot\frac{dy}{dt}
$$
It is getting confusing to me. I used to make a tree diagram to make it a bit easier but this time, it is out of my reach. Can someone give me a hint?

答:
Note that
\begin{eqnarray*}
w\to \left\{\begin{aligned} \color{blue}{x \to x=(t)} \\ \color{red}{ y \to y=(t)} \\ \color{green}{ z \to z= z(x,y) \to \left\{\begin{aligned} \color{blue}{x\to x(t)} \\ \color{red}{y \to y(t)}\end{aligned} \right.} \\  \end{aligned}\right.
\end{eqnarray*}
Now, by chain rule, you have
$$\frac{\partial w}{\partial t}=\frac{\partial w}{\partial x}\color{blue}{\frac{dx}{dt}}+\frac{\partial w}{\partial y}\color{red}{\frac{dy}{dt}}+\frac{\partial w}{\partial z}\color{\green}{\frac{\partial z}{\partial x}}\color{blue}{\frac{dx}{dt}}+\frac{\partial w}{\partial z}\color{\green}{\frac{\partial z}{\partial y}}\color{red}{\frac{dy}{dt}}$$

Title: Tree diagram Chain Rule


问:
Non existence of continuously differentiable function.
Prove that there doesn't exist any function $f: \Bbb {R}\rightarrow\Bbb R $ such that $f(0) =1$  and  $ f'(x) =\int_0^x (f(t))^2  \  dt$

My try:

Clearly $f'(x) \geq 0 $ that implies $ f(x) \geq 1+x$, and similarly one can prove $f(x) \geq 1+p(x)  $   where $p(x) $ is polynomial of arbitrarily large degree.

答:
Clearly $f$ is $C^2$ and $f''=f^2$. Assume that $f$ is defined on $[0,\infty)$, then it's easy to see that $f$ is a $C^2$-diffeomorphism $(0,\infty) \rightarrow (1,\infty)$. Multiplicating the above ODE on $f$ with $f'$ and integrating, one finds that $\frac{f^3}{3}-\frac{f'^2}{2}=\frac{1}{3}$.

Therefore, for any $t \geq 0$, $f'(t) = \sqrt{\frac{2(f(t)^3-1)}{3}}$. Now, let $x > 1$, then $$f^{-1}(x) = \int_1^x{(f^{-1})'(t)dt} = \int_1^x{\frac{dt}{f'(f^{-1}(t))}} = \sqrt{3}\int_1^x{\frac{dt}{\sqrt{2(t^3-1)}}}.$$

This integral is convergent over $[0,\infty)$, therefore $f^{-1}$ is bounded. We get a contradiction.


问:
Proving $f^{(n)} (0)$ s unbounded where $f(x)= \tan^{-1} x$
The following question was asked in real analysis quiz and I am looking for an more elegant solution.

Question :Let $f(x)= \tan^{-1}x $ for all $x\in \mathbb{R}$. Prove that sequence $\{f^{(n)}(0)\}$ is unbounded.

There is a solution given by differentiating $n$ times the expression $(1+x^2) f(x)$ and then using the recurrence relation $(1+x^2) f^{(n+1)} (x)+ 2nx f^{(n)} (x) + n(n-1) f^{(n-1)} (x)=0$ and $f'(0)=1$. But is there a more elegant solution using any other concepts of other branches of pure mathematics or analysis (real, complex, functional).

I thought I should ask here as I don't wanted to use that method although that is clear to me!

Body:
From
$$f'(x)={1\over 1+x^2}=1-x^2+x^4-x^6+x^8-\ldots\qquad(-1<x<1)$$
we obtain
$$f^{(2n+1)}(0)=(-1)^n(2n)!\quad .$$


问:
$g(x) := \sum_{k=1}^\infty (f(x))^k < \infty.$ Show that $g$ is continuous.

Let $f: \Bbb R \to [0,\infty)$ be continuous and assume that for any $x \in \Bbb R$,
$$g(x) := \sum_{k=1}^\infty (f(x))^k < \infty.$$
Show that $g$ is continuous.

My try: For any interval $[-k,k]$, we have $\sup_{\{x\in [-k,k]\}}f(x)=f(y)$ for some $y \in [-k,k]$ and $f(y)<1$ otherwise
$$ g(y) := \sum_{k=1}^\infty (f(y))^k = \infty.
$$
a contradiction. Hence on $[-k,k]$ $$ g(x) := \sum_{k=1}^\infty (f(x))^k \leq \sum_{k=1}^\infty (f(y))^k =\frac{1}{1-f(y)}< \infty.$$ So we can take $M_k:=\sum_{k=1}^\infty (f(y))^k $ and use Weirstrass M test to conclude $S_n(x)=\sum_{k=1}^n (f(x))^k$ converges uniformly to a continuous function $g(x)$ for all $x\in [-k,k]$ now taking $k \to \infty$ we are done.

Is there any other proof that you can think of?

答:
You can do it more directly, otherwise it's ok except for a missing $f(x)$ in the numerator.

The hypothesis about the pointwise convergence series is equivalent to $\forall x\in\Bbb{R}$, $0\leq f(x)<1$. Then for all $x\in\Bbb{R}$, $g(x)=\frac{f(x)}{1-f(x)}$ which is continuous as a composite of continuous maps.


答:
If such $f$ existed, then it would be twice differentiable, since
$$
f'(x)=\int_0^x (f(t))^2\,dt, \tag{1}
$$
and the right hand side is differentiable. Hence $f$ would satisfy the IVP:
$$
f(0)=1,\quad f'(0)=\int_0^0 (f(t))^2\,dt =0, \quad f''(x)=\big(f(x)\big)^2.
$$
Then
$$
f''(x)f'(x)=\big(f(x)\big)^2f'(x) \quad\Longrightarrow\quad
\frac{1}{2}\Big(\big(f'(x)\big)^2\Big)'=\frac{1}{3}\Big(\big(f(x)\big)^3\Big)' \\
\quad\Longrightarrow\quad
\frac{1}{2}\big(f'(x)\big)^2=\frac{1}{3}\big(f(x)\big)^3-\frac{1}{3}
\quad\Longrightarrow\quad f'(x)=\frac{2}{3}\sqrt[3]{\big(f(x)\big)^3-1}
$$
The second "$\Longrightarrow$" since $f(0)=1$ and $f'(0)=0$.

Clearly, $f(0)=1$ implies that $f(x)>0$, positive near $x=0$, and hence
$f'(x)>0$, for all $x>0$, due to (1). Thus $f$ is strictly increasing. If $x_0>0$, then $f(x) \ge f(x_0)=y_0>1$, for all $x\ge x_0$ and
$$
f'(x)=\frac{2}{3}\sqrt{\big(f(x)\big)^3-1}\quad\Longrightarrow\quad
\frac{f'(x)}{\sqrt{\big(f(x)\big)^3-1}}=\frac{2}{3}
\quad\Longrightarrow\quad \int_{x_0}^x \frac{f'(t)\,dt}{\sqrt{\big(f(t)\big)^3-1}}=\frac{2(x-x_0)}{3}
$$
Set
$$
F(y)=\int_{y_0}^{y}\frac{ds}{\sqrt{s^3-1}}<\int_{y_0}^{\infty}\frac{ds}{\sqrt{s^3-1}}=M<\infty.
$$
Hence
$$
M>\int_{f(x_0)}^{f(x)}\frac{ds}{\sqrt{s^3-1}}=\int_{x_0}^x \frac{f'(t)\,dt}{\sqrt{\big(f(t)\big)^3-1}}=\frac{2(x-x_0)}{3}
$$
Contradiction, since the right hand side of the above tends to infinity, as $x\to \infty$.

Title: Non existence of continuously differentiable function.

Body:
Prove that there doesn't exist any function $f: \Bbb {R}\rightarrow\Bbb R $ such that $f(0) =1$  and  $ f'(x) =\int_0^x (f(t))^2  \  dt$

My try:

Clearly $f'(x) \geq 0 $ that implies $ f(x) \geq 1+x$, and similarly one can prove $f(x) \geq 1+p(x)  $   where $p(x) $ is polynomial of arbitrarily large degree.


问:
A mapping that converts a line segment to an arc
I'm looking for a mapping $f:\mathbb{R}^2\to\mathbb{R}^2$ that converts a line segment $AA'$ with two end points $A=(x_A,y_A)$ and $A=(x_{A'},y_{A'})$ to an arc $BB'$ with radius $r$ centered at $O$, with end points $B=(x_B,y_B)$ and $B'=(x_{B'},y_{B'})$.

This mapping should map $A$ to $B$ and $A'$ to $B'$. Does anyone know a closed-form relation for such mapping?

I know that mappings such as $w=1/z$ in complex plain can convert lines to circles. But I don't know how to modify this to convert a particular line segment to an arc given the endpoints and radius.

答:
CAUTION: I have most parts of the answer, except for the final map at the end.  I will update once I figure it out

Let's treat as complex plane.

First, notice that the unit line segment $L=[0,1]$ can be mapped an arc of the unit circle from angle $\theta_1$ to $\theta_2$ where $0 \leq \theta_1 \leq \theta_2 \leq 2\pi$, denoted $S(\theta_1 , \theta_2)$, via the parameterization $f(t ; \theta_1, \theta_2) : L \to S(\theta_1 , \theta_2)$ defined by
$$ f(t ; \theta_1, \theta_2) =  \exp[ i ( \theta_1 (1-t) + \theta_2 t ) ] .$$

So your arc $BB'$ with radius $r$ centered at the origin is obtained from $\mathbf{L}$ by the map
$$ t \mapsto r \cdot f(t ; \theta_1, \theta_2) .$$

All that is left to do is figure out how to map $AA'$ to $L$. Still working on that, should be some kind of rotation, translation, and scaling


问:
Solving the congruence $7x + 3 = 1 \mod 31$?
I am having a problem when the LHS has an addition function; if the question is just a multiple of $x$ it's fine.

But when I have questions like $3x+3$ or $4x+7$, I don't seem to get the right answer at the end.

答:
Since I'm just expanding on J. W. Tanner's one line answer, I am marking this as community wiki.

When trying to solve an equation in $x$ the first thing you try to do is to isolate $x$ on the lhs of the equation; attempt the same when working in modular systems of arithmetic.

So as explained in other answers, you start with the easy part,

$7x + 3 \equiv 1 \pmod{31} \text{ iff } 7x\equiv -2\pmod{31}$

Also, when working with a linear congruence you might as well get rid of any minus signs. So, you want to solve

$\tag 1 7x\equiv 29\pmod{31}$

To complete the job of isolating $x$ you can be proceed as in ordinary algebra by multiplying both sides of $\text{(1)}$ with the inverse of $[7]$. But also, if $\text{(1)}$ is true we can write

$\quad 7x = 29 + 31k$

So to find (the minimal) integer $x$ keep adding $31$ to $29$ until you get a number divisible by $7$ (see J. W. Tanner's answer).


问:
Torque, beam problem.
The length of the beam is L, mass of the beam m, there is a hinge at the origin O

Equilibrium conditions gives
$\sum\limits_{i=1}^n \textbf{F}_i=0$ and $\sum\limits_{i=1}^n \Gamma_i=0$

Position vectors are $\textbf{r}_R=0$, $\textbf{r}_W=\frac{1}{2}L\textbf{i}$, $\textbf{r}_T=L\textbf{i}$

$\textbf{W}=-mg\textbf{j}$

$\textbf{R}=R_i\textbf{i}+R_j\textbf{j}$

$\textbf{T}=|\textbf{T}|\cos(\alpha)\textbf{i}+|\textbf{T}|\sin(\alpha)\textbf{j}$

Torques are

$\Gamma_R=\textbf{0}$

$\Gamma_W=\textbf{r}_W\times\textbf{W}= \frac{1}{2}L\textbf{i}\times(-mg\textbf{j})=-\frac{1}{2}Lmg\textbf{k}$

$\Gamma_T=\textbf{r}_T\times \textbf{T} = L\textbf{i}\times (|\textbf{T}|\cos(\alpha)\textbf{i}+|\textbf{T}|\sin(\alpha)\textbf{j})=L|\textbf{T}|\sin(\alpha)\textbf{k}$

Resolving the second equilbrium condition in the $\textbf{k}$-direction gives $L|\textbf{T}|\sin(\alpha)-\frac{1}{2}Lmg=0$, hence

$|\textbf{T}|=\frac{1}{2}mg \csc(\alpha)$

Resolving the first equilibrium condition in the $\textbf{i}$ and $\textbf{j}$-direction gives

$R_i+|\textbf{T}|\cos(\alpha)=0$

$R_j+|\textbf{T}|\sin(\alpha)-mg=0$

Hence

$R_i=-|\textbf{T}|\cos(\alpha)=-\frac{1}{2}mg\cot(\alpha)$

$R_j=mg-|\textbf{T}|\sin(\alpha)=mg-\frac{1}{2}mg=\frac{1}{2}mg$

Therefore $\textbf{R}=-\frac{1}{2}mg\cot(\alpha)\textbf{i}+\frac{1}{2}mg\textbf{j}$

From the first equilibrium condition, the tension in the string is

$\textbf{T}=-\textbf{R}-\textbf{W}=\frac{1}{2}mg\cot(\alpha)\textbf{i}-\frac{1}{2}mg\textbf{j}+mg\textbf{j}=\frac{1}{2}mg\cot(\alpha)\textbf{i}+\frac{1}{2}mg\textbf{j}$

Ive convinced myself that I have the force $\textbf{T}$ wrong, can anyone confirm that?

答:
Given the forces an the respective application points

$$
\cases{O\to \vec R\\
A\to \vec W\\
B\to \vec T}
$$

the static equilibrium needs

$$
\cases{
\vec R + \vec W + \vec T = 0\\
(A-O)\wedge\vec W+(B-O)\wedge \vec T = 0
}
$$

Here

$$
\cases{
O = (0,0)\\
A = (\frac L2,0)\\
B = (L,0)\\
\vec R = (R_x,R_y)\\
\vec W = mg(0,-1)\\
\vec T = T_0(\cos\alpha,\sin\alpha)
}
$$
resulting into the linear system

$$
\cases{
R_x+T_0\cos\alpha = 0\\
R_y-m g+T_0\cos\alpha = 0\\
T_0\sin\alpha-\frac 12 mg = 0
}
$$

three equations and three unknowns $R_x,R_y,T_0$

and consequently

$$
\cases{R_x = -\frac 12 m g \cot\alpha\\
R_y = \frac 12 m g\\
T_0 = \frac 12 \frac{m g}{\sin\alpha}
}
$$

Title: Torque, beam problem.


问:
A ring in which every non-invertible element is nilpotent
Let $R$ be a ring with an identity element $1$ and with a zero element $0$. We shall say that an element $a\in R$ is a nilpotent if there exist a positive integer $m$ such that $a^m=0$. Clearly, every nilpotent element is not invertible.

Is there a characterization of a ring in which every non-invertible element is nilpotent? The rings $\mathbb Z/(p^a)$, where $p$ is a prime, are examples of such rings. Moreover, in such rings, $x$ is invertible if and only if $1-x$ is not invertible.

答:
Let $a$ be a nilpotent element with degree of nilpotency $n$ in $R$, and $r$ be any other element in $R$.

It cannot be that $ar$ is a unit, for if $ar=u$, then $0=a^nr=a^{n-1}u$, but since $a^{n-1}$ is nonzero by assumption, multiplying it by a unit would be nonzero too.  Therefore $ar$ is nilpotent.  It follows that $1-ar$ is a unit for any $r$, and by a well-known characterization of the Jacobson radical, $a\in J(R)$.  So $J(R)$ contains all the nilpotent elements, and consisting of nonunits itself, it is a nil ideal, so it is in fact equal to the set of all nilpotent elements.

By another well-known exercise, when the nonunits are closed under addition (as is the case here, the nonunits=nilpotents are closed under addition), $R$ is a local ring.

So the characterization is: $R$ is a local ring with nil Jacobson radical.

For commutative rings the situation is slightly easier, because you get that the nilpotents form an ideal for free.

Moreover, in such rings,  is invertible if and only if 1− is not invertible.

That isn't true though. For $R=F_3$, $2$ is invertible and so is $1-2=2$.

What is true is that at least one of $x$ and $1-x$ is a unit (this is another way to characterize local rings.)


问:
Weak law of large numbers - problems
I am currently studying the weak law of large numbers and I have understood the concept behind it. If we take a sample that is enoughly big, the mean of this sample will converge to the sequence of random variables X1,...,Xn that would be very convenient because most of the time. The sequence of random variables called Population is too big to be observed.

My problem is : I cannot find a proper example, problem that uses this theorem. All I found is the proof of it which is not required at this time of my course because my professor has not introduced the Chebyshev inequality...

Could you post here small problemss that I could work on to grasp and practice the mechanic behind the concept ?

Thank you very much

答:
Let's take a fair coin and set $H=1$ and $T=0$

the random variable is the following

$$X=
\begin{cases}
\frac{1}{2},  & \text{if $X=0$} \\
\frac{1}{2},  & \text{if $X=1$}
\end{cases}$$

We have $\mathbb{E}[X]=\frac{1}{2}$ and $\mathbb{V}[X]=\frac{1}{4}$

Now let's take the rv $\overline{X}_n$, the sample mean. You surely know that

$\mathbb{E}[\overline{X}_n]=\frac{1}{2}$ and $\mathbb{V}[\overline{X}_n]=\frac{1}{4n}$

Thus the mean of the sample mean is $\frac{1}{2}$ and its variance is going to zero as $n \rightarrow +\infty$

Thus you can realize that the sample mean "converges" in probability to the population mean, $\frac{1}{2}$ as its variance is very very close to zero.

Formally these condition on mean and variance is an iff condition for the convergence in $L^2$ which implies the convergence in probability

Title: Weak law of large numbers - problems


问:
Is the derivative related to the concept of tangent $n$th-dimensional spaces?
I'm beginning Spivak's Calculus on Manifolds and I'm trying to wrap my head around the concept of a derivative as generalized into higher dimensions. I understand that it is a linear transformation, but I have a couple of questions as to how it is a generalization of the one-dimensional case.

If the function goes $\mathbb{R}\rightarrow \mathbb{R}^2$ then it makes sense to speak of the tangent line to the three-dimensional curve drawn by $f$. Given a function $f:\mathbb{R}^2\rightarrow \mathbb{R}$ it makes sense to ask about the inclination of a plane at any point $a\in \mathbb{R}^2$ in which case one could describe the inclination of the plane by means of the partial derivatives with respect to $x$ and $y$, since the inclination in these two directions already fixes the inclination of the plane. I believe this idea can be generalized to describe the $n$th-dimensional space parallel to the function $f:\mathbb{R}^n\rightarrow \mathbb{R}$.

Can this idea of tangent spaces be extended to functions $\mathbb{R}^n\rightarrow \mathbb{R}^m$?

And since, in the one-dimensional case, the derivative is often interpreted as describing the inclination of the curve at any point $a$ in the domain, is the derivative in higher dimensions somehow related to the concept of tangent lines, planes, or $n$th-dimensional spaces?

答:
The concept generalizes in a completely straightforward way, with the largest difference mostly being that you can no longer draw the higher dimensional pictures. Let's formalize the geometric tangent plane as follows.

Let $f:\mathbb{R}^m \rightarrow \mathbb{R}^n$ be a differentiable function. We consider the graph $\Gamma_f$ of the function as the set of points $(\mathbf{x},f(\mathbf{x})) \in \mathbb{R}^m \times \mathbb{R}^n$. The tangent plane to a point $(\mathbf{x}_0,f(\mathbf{x}_0)) \in \Gamma_f$ is then defined by the set of points $(\mathbf{x},D_{\mathbf{x}_0}f(\mathbf{x}-\mathbf{x}_0) + f(\mathbf{x}_0))$, where $D_{\mathbf{x}_0}f:\mathbb{R}^m \rightarrow \mathbb{R}^n$ is the derivative of $f$ at $\mathbf{x}_0$.

For example, given a function $f:\mathbb{R}\rightarrow \mathbb{R}$, this reduces to your regular notion of the tangent line given by
$$y = \frac{df}{dx}(x-x_0) + f(x_0).$$
In general, given a function $f:\mathbb{R}^m \rightarrow \mathbb{R}^n$, the tangent plane will be an $m$-dimensional plane which sits within the ambient space $\mathbb{R}^m \times \mathbb{R}^n$. Given a function $f:\mathbb{R}^2 \rightarrow \mathbb{R}$ for example, the tangent plane is a $2$-dimensional plane defined within $\mathbb{R}^2\times \mathbb{R} \cong \mathbb{R}^3$, as you can see through explicit drawings.

All of this is really saying that the derivative is the linear mapping which best approximates a given function in some local neighborhood. The derivative matrix of $f:\mathbb{R}^m \rightarrow \mathbb{R}^n$ is an $m \times n$ matrix whose $(i,j)$th component tells you how much the tangent plane is inclined in the $j$th direction of the codomain space $\mathbb{R}^n$ when moving in the $i$th direction of the domain space $\mathbb{R}^m$.

Let me finally note that this geometric view of tangent planes is very useful for intuition, but often not so useful in practice. I've been careful to call the objects I've defined tangent planes, because tangent spaces are refer to another concept with precise meaning in differential geometry. Tangent spaces are abstract formalizations of linearizations of smooth manifolds, and derivatives are really linear maps between the tangent spaces of respective manifolds. I think Spivak's book introduces the concept of tangent spaces in the last few chapters.


答:
If $f:X\to Y$ is Lipschitz, with Lipschitz constant $K$, then $f$ is uniformly continuous, since if $\epsilon>0$ is given, then for $\delta = \frac{\epsilon }{K}$ it holds that for all $x,y\in X$ with $d(x,y)<\delta $, $$d(f(x),f(y))\le K\cdot d(x,y)=K\cdot \frac{\epsilon}{K}=\epsilon.$$

Since any uniformly continuous function is continuous (this follows immediately from the respective definitions), the claim is proved.

Title: Help making Lipschitz proof rigorous

Body:
A function $f:R→R$ is defined to be Lipschitz if there is a constant $K>0$ such that for all $a,b∈R$ $$|f(a)−f(b)|≤K|a−b|$$

Suppose $f:R→R$ is Lipschitz. Prove that $f$ is continuous.

Could someone please verify that my solution is completely rigorous? I think that there may be a slight problem with my proof since I used $|x-y|<δ$ and not $0<|x-y|<δ$. If this means that the proof is not rigorous, I would very much appreciate it if someone could fix the proof so that it is rigorous. Thanks in advance!


问:
Convert to a compact form
I'm trying to help someone regarding Maclaurin Series. It's been a few years since i've done formal maths, and (in fact i used python to compute the derivatives) the series is

$$ 2x-\frac{8}{3}x^3+\frac{32}{5}x^5-\frac{128}{7}x^7+\frac{512}{9}x^9+\ldots \: $$

How do i write this as a summation?

What i know:

Every even term is zero

The sign alternates

The numerator is simply $2^n.$

Title: Convert to a compact form

Body: $$\sum _{n=1}^{\infty } \frac{(-1)^{n+1} 2^{2 n-1} x^{2 n-1}}{2 n-1}=\arctan(2x)$$


问:
$n$ balls into $k$ baskets, $n \geq k$, no empty baskets
I have $n$ balls and throw them into $k$ baskets.

None of $k$ baskets should be empty. Which means each basket has at least one ball.

Balls and baskets are not distinguishable.

What is the number of cases of distribution of balls? And what is the number of each case?

I would be thankful if giving some rationale rather than just a formulae.

答:
As others have mentioned, this is an additive number theory problem. In general there are no nice, explicit formulas for these types of problems. Ramanujan and Hardy worked out an amazing asymptotic formulas for p(n). There are, however, a ton of recursive formulas that when applied, give you explicit formulas for fixed k.

Let $p_k(n)=$ the number of ways to partition n into k parts. Then:

$p_k(n)=p_k(n-k) + p_{k-1}(n-1)$


问:
Duality in robust optimization
I only know that:

for an LP standard primal $\left\{\begin{matrix}
\underset{x}{\operatorname{max}}[c^Tx]\\
Ax \leq b\\
x \geq 0
\end{matrix}\right.$ corresponds the LP dual $\left\{\begin{matrix}
\underset{y}{\operatorname{min}}[b^Ty]\\
A^Ty \geq c\\
y \geq 0
\end{matrix}\right.$;

strong LP duality states that, if the primal admits optimal solution $x$, dual admits optimal solution $y$ and results $c^Tx=b^Ty$. And similarly, weak LP duality states $c^Tx \leq b^Ty$.

Unfortunately, as explained here at page 4, to pass from (3) to (6) we need to use respectively conic and Fenchel's duality. I don't know anything about that, with many thanks to my professor, so I can't figure out this proof.

Could you help me? Every link is also welcome.

Thanks in advance.

答:
you can write

$(a + P\zeta )^T x \le d, \quad \forall \zeta \in Z$

as

$a^T x + (P\zeta )^T x \le d, \quad \forall \zeta \in Z$

Since this must hold for any $\zeta \in Z$, it also holds for the max of $\zeta$ in $Z$. Hence (4).

Then take the dual of the max problem (you know how to do this, use your first message). Hence (5).

They then say: we want $min_{w \in W} f(w) \le p$, that is there must exist $\bar{w} \in W$ such that $f(\bar{w}) \le p$.

So nothing fancy :)

OwnerDisplayName: Marco Pittella

Title: Duality in robust optimization


问:
With Gauss-Jordan there is only one Polynomial
I have a problem to find the answer to this:

$x₁,x₂,x₃ \in \mathbb{R}$ where $x₁<x₂<x_3$ and $y₁,y₂,y₃ \in \mathbb{R}$. With Gauss-Jordan I would like to show that exist only one Polynome $p \in \mathbb{R[x]_2}$ where $p(x_i)=y_i$ with $i=1,2,3$.

I thought to do like this:

\begin{equation}
\begin{bmatrix}
    a_{11} & a_{12}&a_{13} \\
    a_{21} & a_{22}&a_{23} \\
    a_{31} & a_{32}&a_{33}
\end{bmatrix}
\cdot
\begin{pmatrix}
   x_1 \\
   x₂ \\
   x_3
\end{pmatrix}
=\begin{pmatrix}
   y_1 \\
   y₂ \\
   y_3
\end{pmatrix}
\end{equation}
And and I can find the system:

\begin{cases}
  a_{11}x_1 + a_{12}x_2 +a_{13}x_3 &= y_1 \\
       a_{21}x_1 + a_{22}x_2+a_{23}x_3 &= y_2 \\
  a_{31}x₁+a_{32}x_2+a_{33}x_3 &= y_3
\end{cases}

but now I don't know how to show that there is only one polynom.

答:
Hint: write down your polynomial as $p(x)=Ax^2+Bx+C$ so that
$$p(x_i)=Ax_1^2+Bx_1+C=y_1$$
$$p(x_2)=Ax_2^2+Bx_2+C=y_2$$
$$p(x_3)=Ax_3^2+Bx_3+C=y_3$$
holds. This gives you a linear system for $A, B, C$. Do you recognize the form of the matrix? You only need to show that the matrix is invertible in order to know that the system has exactly one solution.


问:
How many Jordan blocks correspond to $\lambda$? What is the intuition?

Let $V$ be a finite-dimensional vector space over $\mathbb{F}$ and $T: V → V$ be linear. Assume that $m_T(t)$ the minimal polynomial splits over $\mathbb{F}$. Show that for any eigenvalue $λ$ of $T$, the number of Jordan blocks corresponding to $λ$ in the Jordan canonical form of $T$ is $\dim\ker(T-\lambda I)$

What is the intuition behind this? I fail to see why this must hold, it seems totally non-intuitive and out of the blue. Could someone help me come up with a proof, and possibly drive some much-needed intuition along the way?

I know that since the minimal polynomial splits over $\mathbb{F}$, $V$ can be written as a direct sum of the generalized eigenspaces $V(\lambda_i)$. Also, $(T-\lambda_iI)$ is nilpotent on $V(\lambda_i)$, so the restriction $(T-\lambda_iI)\vert_{V(\lambda_i)}:V(\lambda_i)\to V(\lambda_i)$ has a Jordan basis (its matrix can be brought to the Jordan normal form). The number of elements in this basis are equal to $\dim V(\lambda_i) = \dim\ker (T-\lambda_iI)^{\dim V}$ which is not necessarily equal to $\dim\ker (T-\lambda_iI)$.

What now? I'm stuck.

答:
Let $J$ be the Jordan form of $T$. In other words, $J$ is in Jordan form and there is an invertible map $S: \Bbb R^n \to V$ for which
$$
T = SJS^{-1}.
$$
With that, it follows that
$$
\begin{align}
\dim \ker(T - \lambda I_V) &=
\dim \ker(SJS^{-1} - \lambda SI_n S^{-1})
\\ &= \dim \ker(S[J - \lambda I_n]S^{-1})
= \dim \ker(J - \lambda I_n).
\end{align}
$$
Now, the question is how $\dim \ker(J - \lambda I_n)$ relates to the structure of the blocks of $J$. Without loss of generality, suppose that the blocks of $J$ are ordered so that
$$
J = \pmatrix{J_1 &0\\0 & J_2},
$$
where $J_1$ consists of all blocks associated with $\lambda$ (and the remaining blocks form $J_2$). We see that $J_2 - \lambda I$ is invertible, which means that $\dim \ker(J - \lambda I) = \dim \ker (J_1 - \lambda I)$.

However, note that $J_1 - \lambda I$ is already in reduced row-echelon form: at the start of each Jordan block, there is a zero-column, and all other columns are pivot-columns. Thus, $\dim \ker(J_1 - \lambda I)$ is simply the total number of Jordan blocks in $J_1$.


问:
hyperbola: equation for tangent lines and normal lines
Find the equations for
(a) the tangent lines, and
(b) the normal lines,
to the hyperbola
$y^2/4 - x^2/2 = 1$ when $x = 4$.</p>

答:
If $x=4, \frac{y^2}4=1+\frac{4^2}2=9\implies y=\pm6$

Using Article 305 of this, the tangent of $$\frac{y^2}4-\frac{x^2}2=1$$
at $(h,k)$  is $$ \frac{y\cdot k}4-\frac{x\cdot h}2=1$$

Do you know how to find the perpendicular of a given line from a given point $(4,\pm 6)$?


答:
Consider a $3\times 3$ Jordan block
$$\begin{pmatrix}\lambda&0&0\\
1&\lambda&0\\
0&1&\lambda
\end{pmatrix}.$$
Now subtract the matrix $\lambda I$ to get the matrix
$$\begin{pmatrix}0&0&0\\
1&0&0\\
0&1&0\end{pmatrix}.$$
Can you see why the kernel of this matrix has dimension $1$?
And if we subtract $\mu I$, where $\mu\neq\lambda$, we get the matrix
$$\begin{pmatrix}\lambda-\mu&0&0\\
1&\lambda-\mu&0\\
0&1&\lambda-\mu\end{pmatrix}.$$
Can you see why the kernel of this matrix has dimension $0$?

This applies to all Jordan blocks. The kernel of $J_\lambda-\lambda I$ for any Jordan block $J_\lambda$ has dimension $1$, always. And the kernel of $J_\lambda-\mu I$ where $\mu\neq0$ has dimension $0$, always. So if we have a block diagonal matrix consisting of only Jordan blocks, each block with eigenvalue $\lambda$ contributes exactly one dimension to the kernel of $T-\lambda I$, and there are no other contributions from the rest of the blocks. So $\dim\ker(T-\lambda I)$ is the number of blocks corresponding to the eigenvalue $\lambda$.

Title: How many Jordan blocks correspond to $\lambda$? What is the intuition?

Body:
Let $V$ be a finite-dimensional vector space over $\mathbb{F}$ and $T: V → V$ be linear. Assume that $m_T(t)$ the minimal polynomial splits over $\mathbb{F}$. Show that for any eigenvalue $λ$ of $T$, the number of Jordan blocks corresponding to $λ$ in the Jordan canonical form of $T$ is $\dim\ker(T-\lambda I)$

What is the intuition behind this? I fail to see why this must hold, it seems totally non-intuitive and out of the blue. Could someone help me come up with a proof, and possibly drive some much-needed intuition along the way?

I know that since the minimal polynomial splits over $\mathbb{F}$, $V$ can be written as a direct sum of the generalized eigenspaces $V(\lambda_i)$. Also, $(T-\lambda_iI)$ is nilpotent on $V(\lambda_i)$, so the restriction $(T-\lambda_iI)\vert_{V(\lambda_i)}:V(\lambda_i)\to V(\lambda_i)$ has a Jordan basis (its matrix can be brought to the Jordan normal form). The number of elements in this basis are equal to $\dim V(\lambda_i) = \dim\ker (T-\lambda_iI)^{\dim V}$ which is not necessarily equal to $\dim\ker (T-\lambda_iI)$.

What now? I'm stuck.


问:
Is this space normed or not?
This particular question was part of my analysis assignment I was unable to prove / disprove it.

Let $V$ denote the vector space of all sequences $a=(a_1 , a_2,...,a_n,...)$ of real numbers such that $\sum_{n\geq 1} 2^n |a_n|$ converges. Define ||.||: $V \to \mathbb{R}$ by $||a|| =\sum_{n\geq 1}2^n |a_n|$. Then is $V$ complete normed space or not.

There were four questions to be answered regarding $V$ . I have done 3 but unable to do this. I know about completely normed space but I was unable to do this . The  idea is to show that every sequence of sequence converges to a limit and that limit is to be constructed or guessed but I am unable to do it

Kindly guide on how this should be done

答:
I'm giving a more basic proof (considering the first two answers). The technique I'm using is rather standard and tries to infer global convergence of a Cauchy family of sequences by analyzing some sort of vertical convergence given componentwise. Let's first prove that  $(V, \| \cdot \|)$ is a normed space. This means that we have to prove first that $\| \cdot \|$ is, in fact, a norm:

Let $a \in V$, if $a \equiv 0$ then $\| a \| = 0$. On the other hand, if $\| a \| = 0$ we can infer that $a \equiv 0$, because otherwise we'll have $a_k \neq 0$ for some $k$ and thus $|a_k| > 0$ which for instance means $\sum_n {2^n} |a_n| \geq {2^k} | a_k| > 0$, a contradiction. The fact that $\| a \| \geq 0$ for all $a \in V$ is trivial. With what we prove, we also have $\| a \| = 0$ iff $a \equiv 0$.

Let $\beta \in \mathbb{R}$ by the fact that  $| \beta a_k |
 = |\beta | |a_k|$ we have, that for any $a \in V$ $\| \beta a \| = | \beta | \| a \|$.  Where $\beta a = (\beta a_1, ..., \beta a_n, ... )$.

The triangle inequality follows the same logic. For, let $a, b \in V$ then, since $|a_k + b_k| \leq |a_k| + |b_k|$ (in the real line) then
$\| a + b \| = \sum_k {2^k} | a_k + b_k| \leq \sum_k {2^k}(|a_k| + |b_k|)$
We conclude with the fact that $\sum_k {2^k}|a_k|, \sum_k {2^k}|b_k| < \infty$.

The steps above ensure that $(V, |\ \cdot \|)$ is a normed space. We need to prove now that this space is complete and we are doing it the long way:

Let $\{a^{(n)}\}_n$ be a Cauchy sequence (sequence of sequences) in $(V, \| \cdot \|)$, here we denote the sequence $a^{(k)}$ by $a^{(k)} = (a_{k1}, a_{k2}, ..., a_{km}, ... )$. I see this kind of sequence as a neverending matrix with components given by $a_{ij}$, where we know that its rows tend to be very similar as we go downwards. The trick here is to find whether there is a way to describe the limit of those rows and then see if it lies in $(V, \| \cdot \|)$.

Let $\varepsilon > 0$, then there exists an $N_{\varepsilon} > 0$ such that for any $n,m > N_{\varepsilon}$ we have:

$$\| a^{(n)} - a^{(m)} \|
< \varepsilon \implies \sum_k {2^k} |a_{nk} - a_{mk}| < \varepsilon$$

Which tell us ${2^k} | a_{nk} - a_{mk} | < \varepsilon$ for any $k \geq 1$. With this in mind, let's define the (vertical) sequences $\{ a_{nk}\}_n$ , and let $\varepsilon_0 > 0$, if we define $\varepsilon = \varepsilon_0 \cdot 2^k$ then, by the above result ($a^{(n)}$ being Cauchy), we have that there exists an $N_{\varepsilon} > 0$ such that for all $n,m > N_{\varepsilon}$ we have

$$| a_{nk} - a_{mk} | <  \varepsilon / 2^k = \varepsilon_0$$

as the above expression is true for any (fixed) $k$, we have that all sequences of the form  $\{ a_{nk}\}_n$ are Cauchy in $(\mathbb{R}, | \cdot |)$ and thus convergent. We can now define the (candidate vertical limit) sequence $b = (b_1, b_2, ..., b_n, ... )$ where $b_k = \lim_{n \to \infty} a_{nk}$. If we manage to prove that $b \in V$ then we finally have that the space is complete.

Let's check if $b \in V$, for that we need $\| b \| < \infty$. In fact,

\begin{equation}
\label{eq:1}
\tag{$\star$}
\|b \| - \| a^{(n)} \| \leq \| b - a^{(n)} \|
\end{equation}

for each $n$, we can zoom in the last term to see

$$\| b - a^{(n)} \| = \sum_k 2^k | b_{k} - a_{nk} |$$

As $\{ a_{nk} \}_n$ converges to $b_k$ for any fixed $k$, we can take $\varepsilon_k = {1} / ({2^k \cdot k^2})$ and find an $N_k$, such that for any $n \geq N_k$, it happens that $2^k | b_{k} - a_{nk} | < 1 / k^2$. With this in mind, let's define $N_l = \sup_{k = 1,..., l} N_k$ and $S_l(n) = \sum_{k = 1}^l 2^k |b_k - a_{nk}|$, then

$$
S_l(N_l) = \sum_{k = 1}^l 2^k |b_k - a_{N_l k}| < \sum_{k=1}^{l} \frac{1}{k^2}
$$

By definition, the sequence $N_l$ is non decreasing in $l$, if it's bounded, then there exists an $N$ such that for any $n \geq N$; $\| b - a^{(n)} \| = \lim_{l \to \infty} S_l(n) <  \sum_{k\geq 1} \frac{1}{2^k} < \infty$. On the other hand, if $N_l$ is not bounded, then as $\lim_{l \to \infty } N_l = \infty$ we substitute $l$ by $N_l$ finding that:
$$
\lim_{N_l \to \infty} \| b - a_{N_l} \| = \lim_{N_l \to \infty} S_{N_l}(N_l) < \sum_{k \geq 1} \frac{1}{k^2} < \infty
$$

Then there exists an $N > 0$ such that,
$$
\| b - a^{(N)} \| < \infty
$$

We conclude using \ref{eq:1}.

Title: Is this space normed or not?


问:
Is the eventown problem solution unique up to isomorphism
Suppose we have a town with a set of residents $X$, where $|X| = n$ (suppose $n$ even for simplicity here). The residents like forming clubs, and we have clubs $C_1,C_2,\ldots,C_m \subseteq X$. The eventown problem is interested in the maximum number of clubs $m$ that can be formed with these specific rules:

All clubs are distinct.

A club must have an even number of members. $\forall i, |C_i|$ is even.

Any pair of two clubs shares an even number of members: $\forall i \neq j, |C_i \cap C_j|$ is even.

It is easy to show that the largest number of clubs possible is $m=2^{n/2}$. An easy construction to attain this bound goes as follow : Take any partition of $X$ into sets of size 2, $B_1,\ldots,B_{n/2}$, and consider the family $\mathcal{F}=\{\bigcup_{i\in S}B_i \ :\ S\subseteq [n/2] \}$

For any partition, this matches the required bound, and all these possibilities are pairwise isomorphic.

Is the solution unique up to isomorphism, or are there some other constructions?

答:
The proof of eventown tells us that at equality, the set of clubs can be represented in $ \mathbb{F}_2^n$, as a linear subspace $F$ of dimension $n/2$ (and $ F = F^\perp$). We will use this context.

Here is a counterexample when $n = 8$.

Let the clubs be spanned by

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

Check that

every vector has 4 1's,

the intersection of any 2 vectors has 2 1's

Linear independence: Vectors 1, 2, 3 are the only ones with a 1 in the last / second last / third last column, so can't be involved in the equation. Hence these vectors are linearly independent.

However, there isn't a pairing that we can do with the first coordinate.

Here is a counterexample when $n = 7$ (so not quite what is asked).

Let the clubs be spanned by

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

Check that

every vector has 4 1's,

the intersection of any 2 vectors has 2 1's

Linear independence: Vectors 1 and 2 are the only ones with a 1 in the last / second last column, so can't be involved in the equation. Hence these vectors are linearly independent.

However, there isn't a pairing that we can do with the first coordinate.


问:
Calculating how many pieces fit into a given area
Is there any program which calculates how many pieces of an item with different sizes you can put in one area?

For example, I have a sheet of glass with size $3210 \times 2210$mm. Now I have different sizes to cut:

$1800 \times 1200=5$pcs,

$600 \times 800=14$pcs,

$400 \times 500=15$pcs,

$900 \times 500=10$pcs.

I want to maximize the use of sheet so to as to avoid big wastage. Can you help me find any program or any formula?

答:
Along the lines of this discussion, I've arrived at the following packing:

I've added the following lines of Javascript to function doRender() in RectanglePacker:

(notice that I scaled down all dimensions by a factor of 10)

```<code>params.canvasWidth = 321;
params.canvasHeight = 221;
var b = []
var i = 0;
var bi = 0;
b[i++] = { w: 180, h: 120, n: 5 };
b[i++] = { w: 60, h: 80, n: 14 };
b[i++] = { w: 40, h: 50, n: 15 };
b[i++] = { w: 90, h: 50, n: 10 };

for (var j=0; j<b.length; j++) {
    for (var n=0; n<b[j].n; n++) {
        blocks[bi++] = { w: b[j].w, h: b[j].h };
    }
}
</code>```

Body:
Along the lines of this discussion, I've arrived at the following packing:

I've added the following lines of Javascript to function doRender() in RectanglePacker:

(notice that I scaled down all dimensions by a factor of 10)

params.canvasWidth = 321;
params.canvasHeight = 221;
var b = []
var i = 0;
var bi = 0;
b[i++] = { w: 180, h: 120, n: 5 };
b[i++] = { w: 60, h: 80, n: 14 };
b[i++] = { w: 40, h: 50, n: 15 };
b[i++] = { w: 90, h: 50, n: 10 };

for (var j=0; j<b.length; j++) {
    for (var n=0; n<b[j].n; n++) {
        blocks[bi++] = { w: b[j].w, h: b[j].h };
    }
}


问:
Different Perspectives of Multinomial Theorem & Partitions
There are 2 important interpretations of the multinomial theorem and coefficients.

1:  Determining the number of ordered strings that can be formed using a set of letters.  For example, with 1 m, 4 i's, 4 s's , and 2 p's, there are $\binom{11}{1,4,4,2}=34,650$ possible 11-letter strings that can be formed, of which mississippi is one specific example.

2: Partitioning a set of objects into several groupings where objects in each grouping are indistinguishable.  For example, in a group of 11 candidates, how many ways can we form 4 committees such that one committee has only 1 member, another has 4 members, another has 4 members, and the fourth committee has 2 members (assuming each person can serve in one committee)?  Again the answer is $\binom{11}{1,4,4,2}=34,650$.  I also understand that multinomial coefficients are a shortcut to partitioning.  We could have equivalently written:  $\binom{11}{1}\binom{10}{4}\binom{6}{4}\binom{2}{2}=34,650$.

I did one problem the other day (Probability/Combinatorics Question), and answered it.  However, I am reviewing the material and seem to get the concepts confused.  In the following question:

At a picnic, there was a bowl of chocolate candy that had 10 pieces of Milky Way, Almond Joy, Butterfinger, Nestle Crunch, Snickers, and Kit Kat. Jen grabbed six pieces at random from this bowl of 60 chocolate candies.

(b) What is the probability that Jen grabs exactly five varieties?

When calculating the numerator of the probability, sometimes I am tempted to write $\binom{6}{2,1,1,1,1,0}$ instead of the correct $\binom{6}{4,1}$.  Sometimes I want to view a type of candy as a committee group.  So since we have 5 varieties, we have 5 committees where one committee has 2 people (or candies), and the rest of the 4 committees have 1 person (or 1 candy).  Can anyone please explain why this is the wrong view and how I can stop confusing myself?

Thank you in advance.

答:
A better way to solve this problem and to evade the confusion that arises is to solve it in 2 parts, so to speak. The first part, will be finding the denominator and this is straight forward, the number of ways in which one can choose 6 out of 60.

The second part, where the numerator is to be determined, we should resort to finding out the number of ways In which we can pick up 5 varieties and one out of the 55 that remain.

This is not as straightforward as the denominator but we can consider the fact that we have complete control over the process and it won't take much time before you realise the numerator is
10^5*55
And the probability comes out to be ~0.1


问:
A condition for the additivity $\mu^{*}(X \cup Y)=\mu^{*}(X)+\mu^{*}(Y)$ in the outer-measure
How can I prove this statement?

Let $X,Y \subseteq \mathbb{R}$ such that $$\overline{X}\cap Y=X \cap \overline{Y}=\emptyset$$
Prove that $$\mu^{*}(X\cup Y)=\mu^{*}(X)+\mu^{*}(Y)$$

Note: Here $\mu^{*}$ is the outer-measure and $\overline{C}$ is the closure of the set $C$.

My attempt:
I know by the sub-addtive property in the outer-measure that $$\mu^{*}(X \cup Y)\leq \mu^{*}(X)+\mu^{*}(Y)$$
Now, by the second inequality, I need to prove that $$\mu^{*}(X\cup Y)\geq \mu^{*}(X)+\mu^{*}(Y)$$
But, I don't know how can I prove that inequality. I think the prove is similar for Carathéodory theorem if I can with the hypothesis to prove that $d(X,Y):=\inf\{|x-y|: x \in X, y\in Y\}>0$, so by Carathéory theorem the prove is immediate, but  I don't know how can I approach that.

答:
I think the following proof is rather inelegant, perhaps someone else can come up with a nicer way:

Let $U = \{(a_i, b_i) : i \in \mathbb{N} \}$ be any basic open cover for $X \cup Y$. The idea is that we want to find a tighter subcovers $U_x$ and $U_y$ of $X$ and $Y$ individually. To that end, let $\tilde{U_x} = \{(a, b) : (a, b) \in U, (a, b) \cap X \not = \emptyset\}$ and $\tilde{U_y}$ defined analogously. Suppose $(a, b) \in \tilde{U_x} \cap \tilde{U_y}$. Thus $(a, b) \cap X, (a, b) \cap Y \not = \emptyset$. Since $(a, b) \cap X \subseteq \mathbb{R}\setminus \overline{Y}$, and the latter is open, that means we may cover $(a, b) \cap X$ in countably many open intervals $\tilde{I_n}$, for $n \in \mathbb{R}$ such that each $\tilde{I_n}$ is disjoint from $\overline{Y}$ and thus $Y$.  Let $I_n = \tilde{I_n} \cap (a, b)$. This is still an interval and the $I_n$ still cover $X \cap (a, b)$. Moreover, $\Sigma_{n \in \mathbb{N}} \mu^* (I_n) \leq \mu (a, b)$ (for a variety of reasons, but if nothing else, each $I_n$ is a lebesgue measurable subset of $(a, b)$). Now replace the entry $(a, b)$ in $\tilde{U_x}$ with $\{I_n\}_{n \in \mathbb{N}}$. Do this for $\tilde{U_Y}$ as well, and do this for every $(a, b) \in \tilde{U_X} \cap \tilde{U_Y}$. You will end up with a resultant $U_X$ and $U_Y$ which are basic open covers of $X$ and $Y$, and moreover, $\Sigma_{(a, b) \in U_X} (b -a) + \Sigma_{(a, b) \in U_Y}(b-a) \leq \Sigma_{(a, b) \in U} (b-a)$ . The only thing to worry about here is the sets $(a, b)$ which were in both $\tilde{U_X}$ and $\tilde{U_Y}$, but we replaced them with intervals $I^{X}_n$ (in the $X$ case) and intervals $I^{Y}_n$ (in the $Y$ case), which are all subsets of $(a, b)$ and thus add up to having less measure than $(a,b)$.

So then $\mu^{*}(X) + \mu^{*}{Y} \leq \Sigma_{(a, b) \in U_X} (b -a) + \Sigma_{(a, b) \in U_Y}(b-a) \leq \Sigma_{(a, b) \in U} (b-a)$.

Which menas that $\mu^{*}(X) + \mu^{*}(Y) \leq \Sigma_{(a, b) \in U}(b - a) $ for an arbitrary basic open cover $U$ of $X \cup Y$, which means tht $\mu^{*}(X) + \mu^{*}(Y) \leq \mu(X \cup Y)$.

I skipped quite a few details in order to keep it from becoming too long. Hopefully the idea remains clear.


问:
Path connected sets (How to intutively find which set is path connected before attempting a formal proof )
I have been preparing for an objective masters exam and  general topology is in the syllabus. The instructor in undergrad course was not interested in teaching and so I self studied and managed to do average level understanding of topology.

Problem arises in path connected set . Proving a set  path connected by definition is not easy and questions are often asked in exam whether a set is path connected or not? But rigorious proof is not asked as I have to just mark the correct options. So, I am asking for if there is some intution .  Consider that  I am given a set and  I have to see whether it's path connected or not , then I can use that intutive method which is less rigorious and time saving also.

If yes , can you tell me by using it on this question : Let A be the following subset of $\mathbb{R}^2$ : A={$(x,y)$:${(x+1)}^2+y^2 \leq  1$} $\bigcup $ {$(x,y): y = x sin(1/x), x>0$}. (This was 1 of the question asked in that exam).

I will apply your method/explanation/intution to other asked question for practice.

I shall be really thankful for any help received!

答:
The crucial step is to get a clear idea of the set in question. In your example it can easily be sketched and seen to consist of a unit disk centred at $\langle-1,0\rangle$ together with what we might call a shrinking topologist’s sine curve. After that it really depends entirely on the set in question; I can’t think of any general principles that are genuinely helpful. In this case, however, it’s not hard.

The origin stands out, because it’s the one point where the disk and the curve meet. If the disk and the curve are both path connected, the whole set should be: for any $p$ and $q$ in the set we should be able to get from $p$ to $q$ by concatenating a path from $p$ to the origin with one from the origin to $q$. (This is inefficient if $p$ and $q$ are on the same side of the origin, but it still works.)

It’s intuitively clear that there is a path from any point of the disk to the origin, since the line segment between the two points lies entirely within the disk. (It wouldn’t even be hard to write the equation of such a path.) And the shrinking sine curve itself provides a path from any point on the right to the origin, so the whole set is indeed path connected.


问:
$\frac{dx}{dt}=\frac{1}{\sqrt{x^3+ax^2+a^2x+a^3}},\text{with } x(0)=x_0>>a, x(T)=a.$ Find an approximation of $T$
So at $x(0)=x_0$ we have:

$\frac{dx(0)}{dt}= \frac{1}{\sqrt{x_0^3+ax_0^2+a^2x_0+a^3}} \approx \frac{1}{\sqrt{x_0^3}}   $ and so $\sqrt{x_0^3}dx(0)=dt$

And at $x(T)=a$ we have:

$\frac{dx(T)}{dt}= \frac{1}{\sqrt{4a^3}} $ and so $\sqrt{4a^3}dx(T)=dt   $

I'm not sure how we can combine this information to get an approximation of $\int_0^Tdt$ (or indeed if using this information is necessary)?

答:
Close to your function:
$$(x+a)^3=(x+a)(x^2+2ax+a^2)=x^3+3ax^2+3a^2x+a^3$$
But the exact factorisation is:
$$x^3+ax^2+a^2x+a^3=(x+a)(x^2+a^2)$$
this tells us that:
$$x'(-a)\to\infty$$
so there is a vertical asymptote as $t=-a$. Also as you said we know that $x'(0)\approx x_0^{-3/2}$. Since the derivative has no other real zeros we can assume that the function $x(t)=0$ has no solutions for $t>0$ and so one way to approximate would be linearly:
$$x(T)=x(0)+x'(0)T$$
$$a\approx x_0+x_0^{-3/2}T$$
giving:
$$T\approx\frac{a-x_0}{x_0^{-3/2}}=x_0^{3/2}(a-x_0)$$


问:
Generate random trees without degree-2 vertices
I am looking for algorithms for the uniform sampling of labelled trees on $n$ vertices with the constraint that none of the vertices should have degree 2. Are there any results for this problem?

Such trees have a Prüfer sequence in which no entry appears precisely once.

For clarification, and example of such a tree is:

答:
One approach is the following:

Pick a uniformly random tree on $n+k$ vertices (we'll pick $k$ later).

If the number of degree-$2$ vertices is not $k$, start over.

For each vertex of degree $2$, replace it by an edge between its endpoints, until there are no such vertices left.

Change the labels from a subset of $\{1,2, \dots, n+k\}$ to $\{1,2,\dots,n\}$, preserving their order.

The result is going to give a uniformly random tree with the constraint, because in each $n$-vertex tree, there are $\binom{n+k}{n}$ ways to undo step 4, and $(n-1)n(n+1)(\dots)(n+k-2)$ ways to undo step 3 (for each vertex of degree 2, in order from smallest to largest, pick an edge to insert it on). So each $n$-vertex tree can be obtained in the same number of ways.

(I guess, equivalently, we could choose a random Prüfer code for an $(n+k)$-vertex tree, and delete the entries that only show up once, changing the labels of the rest in the same way as before. We'd have to be careful to distinguish labels that appeared $0$ times from labels that appeared $1$ time  that we deleted, when we relabel.)

The tricky part is choosing $k$. Each label occurs exactly once in the Prüfer code with probability approximately $\frac 1e$, so the expected number of vertices of degree $2$ is approximately $\frac{n+k}{e}$. This makes it reasonable to choose $k = \lfloor \frac n{e-1}\rfloor$, for example.

The probability of getting exactly $k$ degree-$2$ vertices can be approximated by $\Pr[\text{Binomial}( n+k, \frac1e) = k]$, which is $O(\frac{1}{\sqrt n})$. This is not quite true, because the degrees are not independent, but still suggests that only $O(\sqrt n)$ trials are needed.

Here's a simple implementation using IGraph/M in Mathematica:

```<code>sample[n_] := IGTryUntil[VertexCount[#] == n &] @ IGSmoothen @ IGTreeGame[n + Floor[n/(E - 1)]]
</code>```

A faster, but somewhat less simple version:

```<code>sample2[n_] :=
  With[{k = Floor[n/(E - 1)]},
    IGSmoothen @ IGTryUntil[Count[VertexDegree[#], 2] == k &] @ IGTreeGame[n + k]
  ]
</code>```

Body:
One approach is the following:

Pick a uniformly random tree on $n+k$ vertices (we'll pick $k$ later).

If the number of degree-$2$ vertices is not $k$, start over.

For each vertex of degree $2$, replace it by an edge between its endpoints, until there are no such vertices left.

Change the labels from a subset of $\{1,2, \dots, n+k\}$ to $\{1,2,\dots,n\}$, preserving their order.

The result is going to give a uniformly random tree with the constraint, because in each $n$-vertex tree, there are $\binom{n+k}{n}$ ways to undo step 4, and $(n-1)n(n+1)(\dots)(n+k-2)$ ways to undo step 3 (for each vertex of degree 2, in order from smallest to largest, pick an edge to insert it on). So each $n$-vertex tree can be obtained in the same number of ways.

(I guess, equivalently, we could choose a random Prüfer code for an $(n+k)$-vertex tree, and delete the entries that only show up once, changing the labels of the rest in the same way as before. We'd have to be careful to distinguish labels that appeared $0$ times from labels that appeared $1$ time  that we deleted, when we relabel.)

The tricky part is choosing $k$. Each label occurs exactly once in the Prüfer code with probability approximately $\frac 1e$, so the expected number of vertices of degree $2$ is approximately $\frac{n+k}{e}$. This makes it reasonable to choose $k = \lfloor \frac n{e-1}\rfloor$, for example.

The probability of getting exactly $k$ degree-$2$ vertices can be approximated by $\Pr[\text{Binomial}( n+k, \frac1e) = k]$, which is $O(\frac{1}{\sqrt n})$. This is not quite true, because the degrees are not independent, but still suggests that only $O(\sqrt n)$ trials are needed.

Here's a simple implementation using IGraph/M in Mathematica:

sample[n_] := IGTryUntil[VertexCount[#] == n &] @ IGSmoothen @ IGTreeGame[n + Floor[n/(E - 1)]]

A faster, but somewhat less simple version:

sample2[n_] :=
  With[{k = Floor[n/(E - 1)]},
    IGSmoothen @ IGTryUntil[Count[VertexDegree[#], 2] == k &] @ IGTreeGame[n + k]
  ]


问:
If $X$ is homeomorphic to dense subspace $Y\subseteq X$, then $X=Y$
It is a basic fact of topology that if $X$ is a topological space and $Y\subseteq X$ is homeomorphic to $X$, it does not need to occur that $X=Y$ (for example, $X=\mathbb{R}$, $Y=(0,1)$). My question is, if I add the requirement that $Y$ is dense in $X$. Is this still the case? Or is the following true?

If $X$ is homeomorphic to a dense subspace $Y\subseteq X$, then $X=Y$.

答:
Let $X=\mathbb{Z}$ and $Y=\mathbb{N}$ then $\mathbb{N}\subset \mathbb{Z} $, and define trivial topology $T$=$\{\emptyset,\mathbb{Z} \}$  on $\mathbb{Z}$. Let $x \in \mathbb{Z}$ , then $\forall$ open neighbourhood of $x$ there is non empty intersection with $\mathbb{N}$. Therefore $\mathbb{N}$ dense in $\mathbb{Z}$.
Also let define function $f :\mathbb{N}$ $\rightarrow$ $\mathbb{Z}$ as follows

$f(n) =\begin{cases}
-(n-2)/2,  & \text{if $n$ is even} \\
(n+1)/2, & \text{if $n$ is odd}
\end{cases}$

Therefore $f$ is homeomorphic function. So in here clearly $\mathbb{Z}$ $\neq$ $\mathbb{N}$


问:
Convert two polynomials into a target polynomials through operations

You are provided with two polynomials $x^3-3x^2+2$ and $x^2-4x$ on a
piece of paper.

If there are polynomials $f(x)$ and $g(x)$ on the paper, you are allowed
to write $f(x) + g(x)$, $f(x) - g(x)$, $f(x)g(x)$, $f(g(x))$ and
$cf(x)$.

Can you obtain a linear polynomial (exactly one degree) given
two starting polynomials?

I feel like this could be a linear algebra problem, if the operations are just $f(x) + g(x)$, $f(x) - g(x)$ and $cf(x)$ Then we are looking for the linear dependence. But now sure how to handle $f(x)g(x)$, $f(g(x))$

答:
As mentioned, subtraction decreases the degree if the leading coefficients are the same (which we can ensure with $cf(x)$), so all we need is polynomials of the same degree. This is the crux. See if you can work it out before reading on.

We currently do not have 2 polynomials of the same degree, so let's force them out and take their difference. I will work with the specific cases of $a(x) = x^3 - 3x^2 + 2$, $b(x) = x^2 - 4x$, but I suspect this will generalize (with certain conditions).

Step 1: Calculate $a(x)a(x) = x^6 - 6x^5 + 9x^4 + 4x^3 - 12x^2 + 4$.

Step 2: Calculate $b(x)b(x)b(x) = x^6 - 12x^4 + 48x^2 - 64  $. This gives us 2 polynomials of degree 6.

Step 3: Take their difference $a(x)^2 - b(x)^3 = 6x^5 -39 x^4 + 68x^3 - 12x^2 + 4 = c(x) $.

Step 4: Calculate $a(x) b(x) = x^5 - 7x^4 + 12x^3 + 2x^2 - 8x $. This gives us 2 polynomials of degree 5.

Step 5: Take their difference $ c(x) - 6a(x) b(x) = -15x^4 + 86x^3 - 96x^2 + 48x + 4 = d(x)$.

Step 6: Calculate $b(x) b(x)  = x^4 - 8x^3 + 16x^2$. This gives us 2 polynomials of degree 4.

Step 7: Take their difference $d(x) + 15 6 b(x)b(x) = -34x^3 + 144x^2 + 48x + 4 = e(x) $, which is a polynomial of degree 3.

Step 8: Take their difference $ e(x) + 34 a(x) = 42x^2 + 48x + 72 = f(x) $, which is a polynomial of degree (at most, and hopefully) 2.

Step 9: Take their difference $ f(x)  - 42 b(x) = 216x+72 $, which is a polynomial of degree 1.

Notes

As SenZen mentions, if our initial polynomials don't have a linear term, then none of the operations would have led to a linear term. So this isn't always doable.

As implied by SenZen, we might lower the degree by more than one if the ratio of the first few coefficients are equal. This has happened when I was using $ a(b(x)) , b(a(x))$ as my starting polynomials, and I didn't end up with a polynomial of degree 1.

This process is not unique. We could have made different choices for the polynomials of higher degrees.

I might have a calculation error. If so, let me know. This was way to much calculation for a contest-math problem, even after knowing the crux, so I'd like to know of an alternative solution.


问:
Constructing an example of a cyclic extension of $\mathbb{Q}_5$ of degree $6$ and ramification index $3$
As the title says, I would like to find an example for a cyclic field extension $K/\mathbb{Q}_5$ with $[K:\mathbb{Q}_5]=6$ and $e(K/\mathbb{Q}_5)=3$.

Because this implies that the intertial degree of $K/\mathbb{Q}_5$ must be $2$, the extension $K_0 = \mathbb{Q}_5(\zeta_3)/\mathbb{Q}_5$ (where $\zeta_3$ is a primitive third root of unity) is unramified of degree $2$.

Now I only need to find an element $\alpha$ such that $K=K_0(\alpha)/K_0$ is totally ramified of degree $3$. As this extension must be cyclic (because it has prime degree), the element $\alpha$ must satisfy $\alpha,\alpha^2 \not\in L_0$ but $\alpha_3 \in L_0$. Or one could say that the polynomial $x^3 - \alpha^3$ is irreducible over $L_0[x]$.

I wanted to give $\alpha = \sqrt[3]{2}$ a try (i.e. $\alpha^3 = 2$) and noted that $x^3-2$ has the root $3$ over $\mathbb{F}_5$. This only says that if $\sqrt[3]{2} \in K$, then $K/K_0$ is indeed totally ramified. But this still says nothing about whether $x^3-2$ is irreducible over $K_0[x]$ or not.

Could you please guide me finishing my example?

答:
The result alluded to in reuns' comment can be found in Lang's Algebraic Number Theory, Proposition II.5.12: Let $K$ be a complete, discretely valued field with perfect residue field, and let $p \geq 0$ be the characteristic of the residue field. Let $E/K$ be a field extension that is totally ramified (meaning the degree $[E : K]$ is equal to the ramification index $e$) and tamely ramified (meaning $e$ is not divisible by $p$). Then there exist uniformizers $\pi \in K$ and $\Pi \in E$ satisfying $\Pi^e = \pi$, and so $E \cong K(\pi^{1/e})$.

Thus, if $K$ is any unramified extension of $\mathbb{Q}_5$ and $E/K$ is totally ramified with $e = [E : K]$ coprime to $p$, then $E \cong K((u \cdot 5)^{1/e})$ for some unit $u \in \mathcal{O}_K^\times$. If we allow wild ramification ($p \mid e$), then there are many more possible extensions, but the possibilities for tamely ramified extensions of local fields are very restricted.


问:
Why do the French count so strangely?
Today I've heard a talk about division rules. The lecturer stated that base 12 has a lot of division rules and was therefore commonly used in trade.

English and German name their numbers like they count (with 11 and 12 as exception), but not French:

```<code>  # |   English |           German | French
-----------------------------------------------
  0 |      zero |            null  | zero
  1 |       one |            eins  | un
  2 |       two |            zwei  | deux
  3 |     three |            drei  | trois
  4 |      four |            vier  | quatre
  5 |      five |            fünf  | cinq
  6 |       six |           sechs  | six
  7 |     seven |          sieben  | sept
  8 |     eight |            acht  | huit
  9 |      nine |            neun  | neuf
 10 |       ten |            zehn  | dix
 11 |    eleven |             elf  | onze
 12 |    twelve |           zwölf  | douze
 13 | thir|teen |       drei|zehn  | treize
 14 | four|teen |       vier|zehn  | quatorze
 15 |  fif|teen |       fünf|zehn  | quinze
 16 |  six|teen |       sech|zehn  | seize
 17 |seven|teen |       sieb|zehn  | dix-sept
            18 and 19 are "regular"
 20 |    twenty |          zwanzig | vingt
 21 |twenty-one |  ein|und|zwanzig | vingt et un
 22 |twenty-two | zwei|und|zwanzig | vingt-deux
            23 - 69 are "regular"
 70 |  seven|ty |         sieb|zig | soixante-dix = 60 + 10
              ....
 80 |   eigh|ty |         acht|zig | quatre-vingts = 4*20 ?!?!
 81 |eighty-one |  ein|und|achtzig | quatre-vingt-un = 4*20 + 1
      ...
</code>```

So my question is:

Why do French count so strangely after 79?

(Are there other languages that count similar? What's the historic / mathematical reason for this system?)

Related Questions

Why is a full turn of the circle 360°?

What could be better than base 10?

答:
Actually, if you go back in time a bit in English, you'll realise that English was 'strange' too:

Four score and seven years ago our fathers brought forth on this continent a new nation, conceived in liberty, and dedicated to the proposition that all men are created equal.

(The Gettysberg Address, 1863)

Now if you were to translate that into French in 1863, you'd get pretty much what you'd get today:

Il y a quatre-vingt sept ans, nos pères donnèrent naissance sur ce continent à une nouvelle nation conçue dans la liberté et vouée à la thèse selon laquelle tous les hommes sont créés égaux.

Why this has remained the case in French but has changed in English is probably more of a question for French.SE or English.SE.

Title: Why do the French count so strangely?


问:
Problems that involves two facts in the definition of vector spaces
I have two small questions that I can't solve.

So, there are 8 axioms for vector spaces. One of them is that $1 \cdot a = a$ for all $a \in V$ and of course $1$ is multiplicative identity in $\mathbb{F}.$

How can I be sure this axiom cannot be derived from other 7 axioms?

Also, why is there no definition of $\alpha a= a\alpha, \forall \alpha \in \mathbb{F}, \forall a \in V$? Why is multiplication of scalars and vectors not defined in commutative way?

答: Let $V=\Bbb F^2$. For each $\alpha\in\Bbb F$ and each $(a_1,a_2)\in\Bbb F^2$, define$$\alpha.(a_1,a_2)=(\alpha a_1,0).$$Then $1.(1,1)\ne(1,1)$, but all other aximoms hold for this structure.


问:
Proof Möbius inversion theorem without using Dirichlet convolutions
I’m reading a textbook on number theory and i just finished reading möbius inversion theorem

I also read the proof and fully understand it
But I have a question though

How can I Prove möbius inversion theorem directly and without using Dirichlet convolutions.

Can someone drop a hint or give an answer?

Thanks in advance

答:
It’s mostly just a manipulation of summations. If $g(n)=\sum_{d\mid n}f(d)$, then

$$\begin{align*}
\sum_{d\mid n}\mu(d)g\left(\frac{n}d\right)&=\sum_{d\mid n}\mu(d)\sum_{d'\mid\frac{n}d}f(d')\\
&=\sum_{d\mid n}\sum_{d'\mid\frac{n}d}\mu(d)f(d')\\
&=\sum_{\substack{1\le d,d'\le n\\dd'\mid n}}\mu(d)f(d')\\
&=\sum_{d'\mid n}\sum_{d\mid\frac{n}{d'}}\mu(d)f(d')\\
&=\sum_{d'\mid n}f(d')\sum_{d\mid\frac{n}{d'}}\mu(d)\,.
\end{align*}$$

Now just use the fact that

$$\sum_{d\mid m}\mu(d)=\begin{cases}
1,&\text{if }m=1\\
0,&\text{otherwise,}
\end{cases}$$

which follows easily from the definition of $\mu$ and the fact that $\mu$ is multiplicative, to conclude that

$$\sum_{d\mid n}\mu(d)g\left(\frac{n}d\right)=f(n)\,.$$


问:
Generating Function of P Group
Take G as group of permutations on $n$ elements. It naturally acts on the set $[n]$. Compute the cycle index polynomial of this action of partitioning the permutation into blocks of your own size.

We need to prove that the cycle index polynomial of the above action as
$$P_{G}(x_1, x_2, \ldots x_n) = \sum_{(i)} \frac{\left( \prod_k x_k^{i_k} \right) }{\left( \prod_{k} k^{i_k} i_k! \right)} $$

Here the sum ranges over all partitions $(i)$ represented as $(i_1, i_2, \ldots i_m)$ of $[n]$. Note that $i_k$ is the number of blocks of size $k$ in the partition.

I am unable to get the term in the denominator, can someone help me out?

答:
If I am understanding correctly, you already have used the fact that you can decompose the symmetric group by cycle type. So for a fixed integer partition first select the elements to put in each cycle, so you have
$$\underbrace{\binom{n}{1}\binom{n-1}{1}\cdots \binom{n-i_1+1}{1}}_{i_1\text{ times}}\underbrace{\binom{n}{1}\binom{n-i_1}{2}\cdots \binom{n-i_1-i_2+1}{2}}_{i_2\text{ times}}\cdots $$
which by cancelling out the factorials gives $$\frac{n!}{1!^{i_1}2!^{i_2}\cdots m!^{i_m}}.$$ Now that you have selected the cycles, you have to multiply for in how many ways you can get a cycle of length $j$ the $i_j$ times, that is $(j-1)!^{a_j}$ giving you
$$\frac{n!((1-1)!^{i_1}(2-1)!^{i_2}\cdots (m-1)!^{i_m})}{1!^{i_1}2!^{i_2}\cdots m!^{i_m}}=\frac{n!}{1^{i_1}2^{i_2}\cdots m^{i_m}}.$$
Also, notice that when you selected the $i_j$ cycles, you were giving them an order, you want to take that order out, so yoy have to divide by $i_1!\cdot i_2!\cdots i_m!.$ That gives you the formula you have.

Edit: Remember that two permutations have the same cycle type if they have the same cycle structure in the sense that their share the amount of cycles of size $j$ for every $j.$ So you can decompose the sum in adding the permutations with cycle type $(i_1,\cdots ,i_m)$ where $i_j$ is the number of cycles of length $j.$ Notice that fixed this tuple, you have that $1\cdot i_1+2\cdot i_2+\cdots +m\cdot i_m=n$ because you were partitioning the $n$ elements in these cycles. Then what I explained earlier is how you follow.

Title: Generating Function of P Group


问:
Trying to solve sum binomial expression

I need help to explore the following equalities. In particular I don't get how the second and the third expressions are obtained starting from the first. I've tried to write the terms of the summation, to collect terms and so on but nothing worked. Here the problem:

SECOND EQUALITY SOLVED

$$\displaystyle\sum_{m=M_{jk}}^j {j\choose m} a_j^{m-1}(1-a_j)^{j-m-1}(m-a_jj) \big|_{a_j = 0} =
{j\choose M_{jk}}(1-a_j)^{j-M_{jk}}a_j^{M_{jk}-1}M_{jk}\big|_{a_j = 0} = j I_{\{\gamma_{jk} \leq w_j\}}$$

$M_{jk} = \left \lceil{\frac{\gamma_{jk}}{w_j}}\right \rceil$, $\gamma_{jk}$ and $w_j$ real positive numbers

$a_j\in [0,1] $

$I$ the indicator function

答:
The first equality isn't actually complicated at all. The right side is just the first term of the sum, i.e. with $m=M_{jk}$. For some reason, they chose to evaluate the last factor $(M_{jk}-a_j j)|_{a_j=0} = M_{jk}$. They also wrote $(1-a_j)^{j-M_{jk}}$ instead of $(1-a_j)^{j-M_{jk}-1}$ (probably a typo... but never mind that, since it evaluates to $1$ anyways).

So this is the point: If $m>1$, then $a_j^m = 0$, so the term vanishes. And the only way for $m=1$ to be possible is if $m=M_{jk}=1$, so whatever $M_{jk}$ might be, we only need to look at the first term. Note that $M_{jk}\ge 1$ always.

That said, I think it could have been written in a more consistent or clearer way by the authors...

EDIT: Maybe a point of confusion for you is that they definitely use $a_j=0$ already in the first equality. They just only use on some of the terms.

Title: Trying to solve sum binomial expression


问:
Generating functions for combinatorics
I have no formal education in generating functions, but, based on another question, I have seen that they can be powerful for combinatorics.

Are there a few general principles for using generating functions to construct counting arguments (e.g. counting the number of subsets or number of total orderings) that can be remixed to count different quantities?

If the answer is not amenable to this forum, where can I learn more?

I've been trying to read Concrete Mathematics (Graham, Knuth, Patashnik), but the topic spans several chapters and over 100 pages. At the moment, I just have patience to learn the gist of the combinatorics applications of generating functions. Maybe later I'll go back and get an extensive education from GKP.

答:
There is a very basic introduction available online at http://courses.csail.mit.edu/6.042/fall05/ln11.pdf

You might also find the following link helpful http://www.mathdb.org/notes_download/elementary/algebra/ae_A11.pdf

These notes give you a basic idea of how generating functions are useful for solving simple counting problems. Wilf's Generatingfunctionology is highly recommended if you want a more advanced and in depth treatment of the subject.

Title: Generating functions for combinatorics


问:
Inequality for norms
Let g(x, y) be function on $X\times Y$. Show that for all $p\geq q$
$$
\|\,\|g\|_{L^q(Y)}\,\|_{L^p(X)}\leq \|\,\|g\|_{L^p(X)}\,\|_{L^q(Y)}
$$
Thsnk you.</p>

答:
The Minkowski integral inequality states that for $ r \geq 1 $ and other appropriate conditions we have
$$ \Bigl(\int_X \Bigl|\int_Y f(x,y)dy\Bigr|^r dx\Bigr)^{\frac{1}{r}} \leq \int_Y\Bigl(\int_X |f(x,y)|^rdx\Bigr)^{\frac{1}{r}} dy $$
So you substitute $ f = |g|^q,\ r = p/q $ obtain the inequality and then take $1/q $ power on both sides. This will end up exactly in $ \| \|g\|_{L^q(Y)}\|_{L^p(X)} \leq \| \|g\|_{L^p(X)}\|_{L^q(Y)} $</p>

Title: Inequality for norms


问:
Show that the following sequence of functions converge uniformly to exp(x)
Show that the sequence of functions

$f_n=(1+(exp(1/n)-1)x)^n$ converge uniformly to $exp(x)$ on [0,1].
I tried to differentiate the function to find maximum value but I got stuck .
How should I tackle this problem.
Any hints?

答: My attempt, let $g_{n}=nx(e^{\frac{1}{n}}-1)$ then $f_{n}=(1+\frac{g_{n}}{n})^{n}$ if you can prove that $g_{n}\rightarrow x$ then $f_{n}\rightarrow e^{x}$ we want $n(e^{\frac{1}{n}}-1)\rightarrow 1$ now $u=(e^{\frac{1}{n}}-1)\Rightarrow  $ the limit is the same as $\lim \frac{u}{ln(u+1)}$ and  $u\rightarrow 0$ with  L'Hospitals rule we can easily see $\lim \frac{u}{ln(u+1)}\rightarrow1$


问:
Non existence of continuously differentiable function.
Prove that there doesn't exist any function $f: \Bbb {R}\rightarrow\Bbb R $ such that $f(0) =1$  and  $ f'(x) =\int_0^x (f(t))^2  \  dt$

My try:

Clearly $f'(x) \geq 0 $ that implies $ f(x) \geq 1+x$, and similarly one can prove $f(x) \geq 1+p(x)  $   where $p(x) $ is polynomial of arbitrarily large degree.

答:
The conditions are equivalent to
$$f^{''}(x) = f^2(x)$$
and $f(0)=1$, $f'(0)=0$.

This Cauchy problem has a (unique) local solution defined on an open interval containing $0$. The problem is that it cannot be defined on all $\mathbb{R}$.

Now
$$f{''}(x) = -U'(f(x))$$  (Newton equation of motion, $U$ , the potential  a smooth function ) implies the conservation of energy
$$\frac{1}{2} (f'(x))^2 + U(f(x)) = \textrm{const}$$

Here we get
$$\frac{1}{2}(f'(x))^2 - \frac{f(x)^3}{3} = c $$
so, using $f(0)=1$, $f'(0)=0$
$$(f'(x))^2 = \frac{2}{3}( f(x)^3 - 1)$$

Recall that $f''(x)=f(x)^2\ge 0$, so $f'(x)$ is increasing. Moreover, $f'(0)=0$, therefore, $f'(x) \le 0$ on $(-\infty, 0]$, and $f'(x)\ge 0$ on $[0, \infty)$.

Therefore, on $[0, \infty)$ we have
$$\frac{df}{dx} = (\frac{2}{3}(f^3(x)-1)^{\frac{1}{2}}$$
or
$$\frac{df}{\sqrt{\frac{2}{3}(f^3-1)}}= dx$$
and, using $f(0) = 1$, we get
$$\int_{1}^{f_0}\frac{df}{\sqrt{\frac{2}{3}(f^3-1)}}  = \int_{0}^{x_0} dx= x_0$$

Now, for $f_0 = \infty$, we get a finite value $x_0$ ( the value of a complete elliptic integral). Conclude that the end of the maximal interval for $f$ is finite.  Notice that $f$ is an even function, same applies for the left end.

$\bf{Added:}$

We have
$$\int_{1}^{\infty} \frac{df}{\sqrt{\frac{2}{3}(f^3-1)}} = \frac{\sqrt{6 π} \cdot \Gamma(7/6)}{\Gamma(2/3)}\equiv 2.97448\ldots= x_{\infty}$$

and the function $f$ is defined on $(-x_{\infty}, x_{\infty})$, with limits $\infty$ at both ends of the interval.

Note that the explicit expression for $f$ involves the inversion of elliptic integrals, and so, elliptic functions. Such a simple problem leads to such complex things...


问:
Is there a formula to check that every subsequent value in a vector is less than the previous (it's possible for equal values to exist)?
I'm trying to set a constraint in an optimization problem where each subsequent value is equal or less than the prior one.  Is there some sort of math trick to formulate this?  I've thought about some sort of product of differences that involves testing for negative values but the issue is that it's ok for the subsequent value to be the same.

I am hoping for a trick other than explicitly stating that each subsequent value must be less than the prior - as then my optimization problem is too complicated.

In other words, for a vector of n values, what's the least amount of tests I need to perform to ensure that the vector is in descending order?  And what are the tests I need?  Only operations allowed are addition, subtraction, power, multiplication or division.  No absolute values, if/then tests, etc...

Thanks!

答:
Interpreting your last paragraph, you seem to want to describe the set $$A=\{\,\mathbf a=(a_ß, a_1,\ldots,a_n)\in\Bbb R^{n+1}\mid a_0\ge a_1\ge a_2\ge \ldots \ge a_n\,\}$$ as intersection of sets of the form
$$ C(f):=\{\,\mathbf a\in\Bbb R^{n+1}\mid f(\mathbf a)\ge 0\,\}$$
where $f$ is a polynomial in $n+1$ variables, and minimize the number of such sets used.
We also let
$$ V(f):=\{\,\mathbf a\in\Bbb R^{n+1}\mid f(\mathbf a)= 0\,\}$$
and note that the boundary of $C(f)$ is a subset of $V(f)$.

Equivalently, we can try to describe the more symmetric set
$$ B=\{\,\mathbf b=(b_1,\ldots,b_{n})\in\Bbb R^{n}\mid b_1\ge0, b_2\ge 0,\ldots, b_{n-1}\ge 0\,\}$$ as
such an intersection and note that $$(a_0,\ldots, a_n)\in A\iff (a_0-a_1,\ldots, a_{n-1}-a_n)\in B.$$
Redefine operators $C$ and $V$ accordingly for polynomials in $n$ variables.

Assume $$B=\bigcap _{i=1}^m C(f_i).$$
Write each $f_i$ as $\sum_{k\ge 0}f_{i,k}$ where $f_{i,k}$ is homogeneous of degree $k$, i.e., $f_{i,k}(\lambda\mathbf x)=\lambda^kf_{i,k}(\mathbf x)$.
If $d_i$ is the maximal degree for which such a summand is not identically zero, then $f_{i,d_i}$ dominates $f_i$ for large $\mathbf x$ and in a definable sense $C(f_i)$ tends to $C(f_{i,d_i})$  large $\mathbf x$. The act that $B$ itself is invariant under scaling with (positive) $\lambda$  then leads to the conclusion that we may assume that $f_i=f_{i,d_i}$, i.e., that wlog the $f_i$ are homogeneous.

The same argument applies to the restrictions of the $f_i$ to some hyperplane $x_1=1$, say. It follows that we may assume that $f_i(1,x_2,\ldots, x_{n})$ is homogeneous in $(x_2,\ldots, x_{n})$, hence also in $x_1$, and by symmetry in every single $x_k$. But then $f_i$ must be a single monomial!

For each $f_i$, let $S_i\subseteq \{1,2,\ldots, n\}$ be the set of indices $k$ such that $f_i$ is odd in $x_k$. Then we can replace $f_i$ with $\pm\prod_{k\in S_i}x_k$ without harm, i.e., for a suitable choice of $\epsilon_i\in\{-1,1\}$, we have
$$B=\bigcap_{i=1}^nC(\epsilon_i\prod_{k\in S_i}x_k ). $$
Consider the $2^{n}$ points $\mathbf x$ with $|x_k|=1$ for all $k$.
$B$ contains exactly one of these, $(1,\ldots,1)$. If we negate $\epsilon_i$ for all $i$ with $x_k\in S_i$, then the resulting intersection will again contain only one such point, namely the one with all entries $=+1$ except $x_k=-1$. By combining similar sign changes, we can adjust the signs $\epsilon_i$ in such a manner that the intersection contains any of our $2^n$ points (and no other). Therefore, we must be able to asign signs in at least $2^n$ ways to the $m$ monomials. In other words,
$$ m\ge n.$$


问:
Why does this limit exist even though there are infinite limiting values?

According to wolfram alpha and my textbook, this limit exists simply by plugging in the values to get 6/5.
However, if you approach along y=mx, then the expression becomes $\frac{2+m^2}{1+m^2}$, which means the limit depends on m and has infinite values, thus does not exist.

My hunch is this reasoning is incorrect because when you set $y=mx$, you aren't actually approaching $(-1,2)$ without limiting m to be $m=-2$.

答: Analysing approaches along lines, you would have to use the equations $y=m(x+1)+2$. Put it in the limit and you will see that it works.


问:
Finding Invariant Factors of a Matrix
I am trying to find the invariant factors of the matrix

$$A = \begin{pmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 3 & 2 & 2 \\ \end{pmatrix}$$

From what I gather, I have to use elementary row operations on $xI - A$ until I obtain a diagonal matrix, and the nonzero diagonal entries form the invariant factors of $A$. Well, I tried this multiple times and these are some of the results of what I got:

$$\begin{pmatrix} (1-x)(x^2-2x) & 0 & 0 \\ 0 & -x^2 + 2x & 0 \\ 0 & 2x + 1 & 2-x \\ \end{pmatrix}$$

$$\begin{pmatrix} (x-1)^3 & 0 & 0 \\ 0 & (x-1)^2 & 0 \\ 0 & 0 & (x-2)(x-1)^3 \\ \end{pmatrix}.$$

$$\begin{pmatrix} (x-1)^3 & 0 & 0 \\ 0 & (x-1)^2 & 0 \\ 0 & 0 & (x-2)(x-1)^3 \\ \end{pmatrix}.$$

But none of these seem right. Either the degree of the polynomials is too high or the right divisibility relation does not hold. I don't know what I am doing wrong. I am very awful at calculating, but I didn't think I was that awful.

Perhaps there is an easier way. I know that the largest invariant factor is the minimal polynomial, and the minimal polynomial divides the characteristic polynomial. A quick calculation (which wolframalpha did for me, because I don't trust myself) reveals that $p_{A}(x) = -x(x-2)^2$ is the minimal polynomial. Clearly $x$ and $x-2$ are not the minimal polynomials of $A$, so $m_A(x) = (x-2)^2$ is the minimal polynomial of $A$. At this point, can I conclude what the invariant factors of $A$ are? I know they have to divide $m_A$.

答:
Here is a quick way to find the invariant factors.

First, compute the characteristic polynomial $p(x) = \det(xI - A) = x(x-2)^2$. Each degree $1$ factor of the characteristic polynomial must be a factor of the minimal polynomial, so the minimal polynomial is either $x(x-2)$ or $x(x-2)^2$.

One way to show that the minimal polynomial is not $x(x-2)$ is to compute $A(A-2I)$ and verify that you do not end up with the zero matrix.

Alternatively, it suffices to find the rank of $A - 2I$. Note that if $A$ has minimal polynomial $x(x-2)$ (i.e. the minimal polynomial is a product of distinct degree one factors), then $A$ must be diagonalizable. This would mean that we have $\dim\ker(A - 0I) + \dim \ker(A - 2 I ) = 3$. We must have $\dim \ker A = 1$ since $0$ is an eigenvalue of algebraic multiplicity $1$. We find that $\dim \ker (A - 2 I) = 1$ (or correspondingly that $A - 2 I$ has rank $2$), which means that the sum of the dimensions of the kernels is not equal to $3$, which means that $A$ is not diagonalizable, which means that the minimal polynomial must be $x(x-2)^2$.

Since the characteristic and minimal polynomials are equal, deduce that $x(x-2)^2$ is the only invariant factor of $A$.

Title: Finding Invariant Factors of a Matrix


答:
In addition to @JPMarciano's answer, I have found that if you let
$y=mx+c$ so that it can truly approach any point, then $y=mx+c$ becomes $m=c-2$ after plugging in (-1,2).
If you then substitute $y=mx+c$ into the original expression you get the following, which evaluates to 6/5!

Title: Why does this limit exist even though there are infinite limiting values?

Body:
According to wolfram alpha and my textbook, this limit exists simply by plugging in the values to get 6/5.
However, if you approach along y=mx, then the expression becomes $\frac{2+m^2}{1+m^2}$, which means the limit depends on m and has infinite values, thus does not exist.

My hunch is this reasoning is incorrect because when you set $y=mx$, you aren't actually approaching $(-1,2)$ without limiting m to be $m=-2$.


问:
Common eigenvector of two linear transformation matrices
I have two linear transformation matrices

\begin{pmatrix}
3 & 2 \\
-2 & 1
\end{pmatrix}

and

\begin{pmatrix}
1-a & -a \\
a & 1
\end{pmatrix}

How to find out what the value of $a$ should be for them to have a common eigenvector?

答:
Find the eigenvectors of the first matrix.

Its characteristic polynomial is $(3-x)(1-x)+4=x^2-4x+7=(x-2)^2+3$, so it has no real root, that is, the matrix --viewed over $\Bbb R$ -- doesn't have any eiginvectors.

Well, over $\Bbb C$, it does have two roots, namely $\lambda_{1,2}=2\pm\sqrt3i$, and you can calculate the corresponding eigenvectors (with necessary complex entries), say they are $v_1$ and $v_2\ \in\Bbb C^2$. Then write up the eigen-equation
$$\pmatrix{1-a&-a\\a&1}v_i\,\parallel\,v_i$$
for both $i=1,2$. Of course, $a=-2$ will be a solution (see comments), but there might be more.