问:
Stuck on an alternating sum of binomial coefficients
Hi I'm currently doing some exercise problems for my first year university math course. The formula I'm supposed to proof is the following:

$$
\sum_{k=0}^n \frac{(-1)^k}{k+1}\binom{n}{k} = \frac{1}{n+1}
$$

I tried using induction, and while the start is easy, I'm not able to proof the implication from $n$ to $n+1$. Using the pattern we learned for those kinds of questions I'd get

$$
\sum_{k=0}^{n+1} \frac{(-1)^k}{k+1}\binom{n+1}{k} = \sum_{k=1}^n \frac{(-1)^k}{k+1}\binom{n+1}{k} + \frac{(-1)^{n+1}}{n+2}\binom{n+1}{k}
$$

The main trouble with that is the $n+1$ in the binomial coefficient where I don't see a way to do induction.

I also thought about multiplying the sum with $n+1$, in the hope that stuff in the sum would cancel out, leaving me with a $1$ at the end, but I didn't progress that way either.

I'd greatly appreciate it if someone could hint me at what I'm missing!

答:
Use
\begin{eqnarray*}
\frac{1}{k+1} = \int_0 ^1 x^k dx.
\end{eqnarray*}
Now should the sum start at $k=0$ ? ... then we have
\begin{eqnarray*}
\sum_{k=0}^{n} \frac{(-1)^k}{k+1} \binom{n}{k} &=& \int_0^1 \sum_{k=0}^{n} \binom{n}{k} (-x)^k  dx \\
&=& \int_0^1 (1-x)^n dx = \frac{1}{n+1}. \\
\end{eqnarray*}


问:
Is $B(H \otimes K)$ generated by $B(H) \otimes B(K)$?
Let $H$ and $K$ be Hilbert spaces and $H \otimes K$ their Hilbert space tensor product.

Given $S \in B(H)$ and $T \in B(K)$, there is a unique operator $S \otimes T \in B(H \otimes K)$ such that
$$(S \otimes T) (h \otimes k) = Sh \otimes Tk, \quad h\in H, k \in K.$$

Is the following equality true?

$$B(H \otimes K) = \overline{\text{span}}\{S \otimes T: S \in B(H), T \in B(K)\}$$

If so, how can one show this?

答:
You need to be careful when you write $B(H)\otimes B(K)$ because, as a C$^*$-algebra, $B(H)$ is not nuclear and so there not a unique tensor norm. The product also makes sense as  von Neumann algebras, in which case it is unique; the latter is the most common interpretation (but then the set in your title and the set in your question are not the same).

The equality is true if you take the sot-closure. In that case the closed span is $B(H)\otimes B(K)$ as von Neumann algebras, and you have $$(B(H)\otimes B(K))'=B(H)'\otimes B(K)'=\mathbb C\otimes \mathbb C,$$ so $B(H)\otimes B(K)=(B(H)\otimes B(K))''=(\mathbb C\otimes \mathbb C)'=B(H\otimes K)$. Alternatively, one can show that rank-one operators in $B(H\otimes K)$ are in $B(H)\odot B(K)$, and so the sot-closure will be everything.

With norm closure, on the other hand, there is no equality. This can be easily seen when both $H,K$ are  separable, from the fact that the C$^*$-algebra $\overline{\operatorname{span}} B(H)\odot B(K)$ has several ideals ($K(H)\otimes B(K)$, $B(H)\otimes K(K)$, $K(H)\otimes K(K)$) while $B(H\otimes K)$ has only one.

Edit: When $H$ is not separable the idea in the last paragraph still works, by noting that  the  ideals of $B(H\otimes K)$  are generated by the operators with rank at most a certain cardinality, while either $K(H)\otimes B(K)$ or $B(H)\otimes K(K)$ will have operators with rank of full cardinality.

ContentLicense: CC BY-SA 4.0


问:
Symmetric matrix and Hermitian matrix, unitarily diagonalizable
If $A$ is an n by n real matrix, then $A$ is Hermitian if and only if $A$ is symmetric.

Is this statement true or false? I think it is true?

Second question: Is every real symmetric matrix unitarily diagonalizable?
This is false right?   I want see some explanation, thank you.

答: Yesi you are right. For second question, I don't know what do you mean by unitarily diagonalizable. Real symmetric matrices are diagonalizable.</p>


Title: Stuck on an alternating sum of binomial coefficients

Body:
Hi I'm currently doing some exercise problems for my first year university math course. The formula I'm supposed to proof is the following:

$$
\sum_{k=0}^n \frac{(-1)^k}{k+1}\binom{n}{k} = \frac{1}{n+1}
$$

I tried using induction, and while the start is easy, I'm not able to proof the implication from $n$ to $n+1$. Using the pattern we learned for those kinds of questions I'd get

$$
\sum_{k=0}^{n+1} \frac{(-1)^k}{k+1}\binom{n+1}{k} = \sum_{k=1}^n \frac{(-1)^k}{k+1}\binom{n+1}{k} + \frac{(-1)^{n+1}}{n+2}\binom{n+1}{k}
$$

The main trouble with that is the $n+1$ in the binomial coefficient where I don't see a way to do induction.

I also thought about multiplying the sum with $n+1$, in the hope that stuff in the sum would cancel out, leaving me with a $1$ at the end, but I didn't progress that way either.

I'd greatly appreciate it if someone could hint me at what I'm missing!

Body: Hint: Use $\frac{n+1}{k+1}\binom{n}{k}=\binom{n+1}{k+1}$


问:
Prime counting function as ratio of polynomials.
I came across this interesting question in an advanced Analytic number theory book

Prove that there are no polynomials $M(x)$ and $N(x)$ such that $\pi(x) = \frac{M(x)}{N(x)}$ for all $x = 1,2,3,\dots$

Suppose there are polynomials $M$ and $N$ such that $\pi(x) = M(x)/N(x)$ , since prime number theorem says that

$$\lim_{x \to \infty} \frac{\pi(x)\log(x)}{x} = 1.$$

Now using this and our previous assumed expression and by using elementary method to calculate limits, we can conclude following things about $M$ and $N$.

$M$ and $N$ have same degree.

$M$ and $N$ have same leading coefficient and obviously $N$ should divide $M$ for each $x$.

This would force me to conclude prime counting function is a constant polynomial since $M$ is multiple of $N$ and they have same degree which is a contradiction to infinitude of prime numbers.

Is this rigorous enough to solve the problem?

I observe here that we used prime number theorem which is very sophisticated tool and certainly non intuitive. Is there any method that doesn't use PNT to solve this problem?

答:
It is elementary to prove that there are arbitrarily long stretches of consecutive composite numbers, e.g., $n!+2, n!+3,n!+4,\ldots,n!+n$ for any $n\ge2$. So if $\pi(x)=M(x)/N(x)$ for all positive integers $x$, with polynomials $M$ and $N$, and $\{k,k+1,k+2,\ldots,k+n\}$ is a prime-free stretch of numbers, then

$$N(k+x)\pi(k)-M(k+x)=0$$

for $x\in\{0,1,2,\ldots,n\}$. Now we cannot have $\pi(k)=M(k+x)/N(k+x)$ for all integers $x$; for example $M(k+(2-k))/N(k+(2-k))=M(2)/N(2)=\pi(2)=1\not=\pi(k)$ in general. Thus $N(k+x)\pi(k)-M(k+x)$ is a nonzero polynomial (in $x$) of degree at most $\max\{\deg(M),\deg(N)\}$. But if the length of our prime-free stretch, $n+1$, exceeds this degree, we have a contradiction.

Remark: This proof has little to do with the infinitude of primes; quite the opposite in fact. It really amounts to showing that any nonconstant rational function has an upper bound (given by the larger degree of its numerator and denominator) on the number of times it can assume any given value. The only relevant properties of the prime counting function that come into play are the fact that $\pi(x)$ is nonconstant but has no upper bound on the number of times it takes the same value (in particular, is constant over arbitrarily long stretches).


问:
Homotopy motivation
Currently, I am working on homotopy. I know the definition of homotopy.
Homotopy is nothing but "continuously deformation" of object.
Therefore we can say triangle and circle are same.
The concept of homotopy is published by L.E.J. Brouwer (1881-1996), he made precise many of the ideas of Henri Poincarè.

I want to know the motivation of Homotopy.
Why we need it?
I look out on wikipedia but I didn't find something related to it.

答:
Here is one reason it turns out to be useful. I won't attempt to be exhaustive, and hopefully other people will also contribute some more ideas.

By construction homotopy is a much coarser invariant than homeomorphism: two spaces which are homeomorphic are trivially homotopy equivalent. On the other hand homotopy does not even preserve basic topological invariants like dimension ($\mathbb{R}^n\simeq\ast$, for instance). While this makes it less appealing to the topologist, the upshot is that homotopy type is generally much easier to compute than homeomorphism type.

However homotopy often turns out to contain exactly the information which is needed in practice. Often difficult topological and geometric problems can be reduced to homotopy-theoretic ones. Once this is done the door is opened for algebraic-topological methods to enter the picture, and there may be pleasant consequences.

For example surfaces are classified by their homotopy type (in fact by their $H_1$'s). As another example, in light of Perelman's solution of the Poincaré conjecture, given a homology 3-sphere, the difficult geometric question of deciding whether it is $S^3$ or not is reduced to the much easier question of calculating its fundamental group.

As a slightly deeper example there are applications to 4-dimensional topology. For example Freeman-Milnor-Whitehead say that two simply connected closed topological 4-manifolds which are homotopy equivalent and share a Kirby-Siebenman invariant, are in fact homeomorphic.

Finally it would be remiss not to mention the Borel conjecture. This asserts that the homeomorphism type of a closed aspherical manifold should be completely determined by its homotopy type. While many special cases of the conjecture have been proved, its full solution is still an open problem.

Title: Homotopy motivation


问:
On proof methodology of Theorem 1.20(b) in Rudin's "Principles of Mathematical Analysis," 3rd edition.
I am studying Rudin's "Principles of Mathematical Analysis," 3rd edition by myself. On reading a few proofs in the book I am getting an idea of the following methodology in proving theorems :

Ask a question. For example, "Is $\mathbb{Q}$ dense in $\mathbb{R}$?"

State what needs to be proved if the answer to the above question is true. In our case,

If $ \in \mathbb{R}$, $y \in \mathbb{R}$, and $<$, then there exists a $p \in \mathbb{Q}$ such that $<<$

If this proposition is disproved then the answer to 1 is NO, otherwise YES

Work backwards and try to find what need to be proved from which 2 can be deduced. In our case,

$\exists  m, n \in \mathbb{Z}, n \ne0: nx < m < ny$

Here we simply applied the definition of a rational number.

Continue this process until you reach a proposition which can be proved/disproved using another theorem or axiom. In our case, Rudin has used the Archimedean Property of $\mathbb{R}$

Write the steps from 4 to 2 (in that order). This completes the proof/disproof.

This methodology appears far convincing to me when compared to knowing the reason behind : "Why Rudin used $n(y-x) > 1$ in the first place?"

I would like to know if this is the right methodology?

答:
This is correct - as far as it goes. But your question

Why Rudin used $n(y−x)>1$ in the first place?

is in a way the crux of the matter. The other steps are the routine part - the framework, as it were. This is the place where you need some actual understanding/intuition about "why" the assertion is correct. That you develop over time, by looking at lots of examples and lots of proofs, trying to reconstruct the ideas, not just check the logic.

Good for you for understanding that when you write the formal proof you write those steps in reverse order - not the way you discovered them.

In "prove or disprove" questions (the most instructive kind) you often find yourself first trying to prove something. If you run into a wall you wonder whether the assertion is true, so you start looking for a counterexample. If you can't find one you go back to looking for a proof. That back and forth continues until you understand the situation.

Finally, an anecdote. Years ago I took advanced calculus from  Lars Ahlfors. He warned us that he did not like proofs that started from the hypotheses and got as far as possible, then from the conclusion reasoning backwards as far as possible, then writing "therefore" where the logical chains met.


问:
Isomorphism of All Simple Graphs with 5 Vertices and 9 Edges
Given the simple graph H with vertex set {a,b,c,d,e} and nine edges consisting of all possible edges except edge {c,e}. Are all simple graphs with five vertices and nine edges isomorphic to H? Why?

I tried solving this by checking every permutation and I think the answer is yes, but my question really is, how can we explain or prove this?

答: Suppose you have two copies of $K_5$.  They're obviously isomorphic, and in fact, every bijection between the vertices is an isomorphism.  Now remove and edge from edge graph.  The two resulting graphs are isomorphic, because there was an isomorphism of the $K_5$ that carried the vertices of one of the removed edges to the vertices of the other.


问:
If $m(Z)=0,W=\{x^2: x\in Z\}$, how to prove that $m(W)=0$?
Here is my question,

If $m(Z)=0, W=\{x^2: x\in Z\}$, how to prove that $m(W)=0$? Here $m$ is the Lebesgue measure.

I have no idea about it, can anyone give me a hint or answer?

答:
Denote $g : x \mapsto x^2$. We have to prove that $m(g(Z)) = 0$. We have $W = \cup_n W_n$ where $W_n = W \cap [n,n+1)$ where $n \in \mathbb N$.

It is enough to prove that for all $n \in \mathbb N$, $m(W_n) = 0$. And this is the case as $W_n = g([\sqrt n, \sqrt{n+1})) \cup g([-\sqrt{n+1}, - \sqrt n))$ and $g$ is absolutely continuous on $[\sqrt n, \sqrt{n+1}), [-\sqrt{n+1}, - \sqrt n)$ as it is Lipschitz continuous on those bounded intervals.


问:
Show that preimage is an embedded surface
I have given a function
$$f:\mathbb{R}^4 \to \mathbb{R}^3: (x,y,z,u) \mapsto (xz-y^2, yu-z^2,xu-yz)$$
and I want to show that $f^{-1}(0)\setminus\{0\}$ is an embedded surface.
If it would be an embedded curve I could verify that $f$ is an submersion to get a 1-dim submanifold. But I don't know how to show that this is an embedded surface.</p>

答:
I saw this problem from Amann's Analysis II, page 257.

Note that
$$\begin{aligned}
y^2&=xz\\
z^2&=yu\\
yz&=xu.
\end{aligned}$$
If $yz\neq 0$, then
$$\begin{aligned}
y^2\cdot yz=xz\cdot xu&\implies y=x^{2/3}\cdot u^{1/3}\\
z^2\cdot yz=yu\cdot xu&\implies z=x^{1/3}\cdot u^{2/3}.
\end{aligned}$$
In the case $yz=0$, then it is easy to see that $xu=0$ and $y=0=z$, where the above relations also hold.

Let $(a,b)=(x^{1/3},u^{1/3})$ and $$g:(a,b)\mapsto (a^3,a^2b,ab^2,b^3).$$
It is clear that $g$ is a homeomorphism.
And $$\partial g=\begin{pmatrix} 3a^2& 0\\ 2ab&a^2\\ b^2&2ab\\ 0&3b^2 \end{pmatrix}$$ and $g$ is an embedding when $(a,b)\neq (0,0)$.

It follows that $g(\mathbb R^2\setminus \{(0,0)\})=f^{-1}(0)\setminus \{0\}$ is a embedded curve.


问:
Mean and variance of a combination of uniform and standard normal random variables.
Let $X$ and $Y$ be two independent random variables. Suppose that $X\sim U(0,1)$ and $Y\sim N(0,1)$. Find the expectation (mean) and variance of $H=Ye^{XY}$.

I have tried to show that the random variables $H$ and $Y$ are independent, which I believe would facilitate the proof. Am I in the right track? Any help is appreciated.

答:
There are several methods you can use to solve the question

You can start with using the definition of expectation

$$\mathbb{E}[Ye^{XY}]=\int_0^{1}\Bigg[\int_{-\infty}^{\infty}y e^{xy}\frac{1}{\sqrt{2\pi}}e^{-\frac{y^2}{2}}dy\Bigg]dx=$$

$$=\int_0^{1}e^{\frac{x^2}{2}}\Bigg[\int_{-\infty}^{\infty}y \frac{1}{\sqrt{2\pi}}e^{-\frac{(y-x)^2}{2}}dy\Bigg]dx=\int_0^1 x e^{\frac{x^2}{2}}dx=\sqrt{e}-1$$

The integral in the $[...]$ braces is $=x$ because it is the expectation of a normal rv $N(x,1)$

Using conditional properties

$$\mathbb{E}[Ye^{XY}]=\mathbb{E}[\mathbb{E}[Ye^{XY}|Y]]=\mathbb{E}[Y\mathbb{E}[e^{XY}|Y]]=\mathbb{E}[e^Y-1])=\sqrt{e}-1$$

and this because

$$\mathbb{E}[e^{XY}|Y=y]=\int_0^1 e^{xy}dx=\frac{e^y}{y}-\frac{1}{y}$$

and going on solving,

$$\mathbb{E}[e^Y-1]=\mathbb{E}[e^Y]-1=\sqrt{e}-1$$

because $e^Y\sim$ lognormal

To calculate the variance calculate first second simple moment with the same procedure than you can get the variance remembering that

$$\mathbb{V}[X]=\mathbb{E}[X^2]-\mathbb{E}^2[X]$$


问:
A bounded linear functional diverges when n $\rightarrow \infty$
Consider the Banach space $C(T)=\{f:[-\frac{1}{2},\frac{1}{2}] \rightarrow \mathbb{C} \}$ with $f$ continuos with the uniform norm
\begin{equation*}
 ||f||= sup_{x \in [-\frac{1}{2},\frac{1}{2}]} |f(x)|
\end{equation*}
For every $f \in C(T)$ define $\hat{f}(k)=\int_{-\frac{1}{2}}^{\frac{1}{2}} e^{-2 \pi i k x}f(x)dx$ where $k \in \mathbb{Z}$, and consider
\begin{equation*}
S_nf(x)=\sum_{k=-n} ^n \hat{f}(k)e ^{2 \pi k ix}
\end{equation*}
Take $x=0$ and define $T_n(f)=S_nf(0)$. I want to show that $||T_n|| \rightarrow \infty$ when $n \rightarrow \infty$. I already proved that $T_n$ is a bounded and linear functional in $C(T)$, i.e, I proved that $||T_n|| \leq 2nf$. I think about delimit that norm below with something that goes to infinity when $n \rightarrow \infty$ but I don't know what limit choose to do that.

答:
Let us begin by analyzing the operators $S_n$,

Theorem.  $\|S_n\|\to\infty$, as $n\to\infty$.

Proof.
Notice that
$$
  S_nf(x)=
  \sum_{k=-n} ^n \hat{f}(k)e ^{2 \pi ikx} = $$$$ =
  \sum_{k=-n} ^n e ^{2 \pi ikx} \int_{-\frac{1}{2}}^{\frac{1}{2}} e^{-2 \pi i k y}f(y)\, dy =  $$$$ =
  \int_{-\frac{1}{2}}^{\frac{1}{2}}  \sum_{k=-n} ^n e ^{2 \pi ik(x-y)} f(y)\, dy.
  $$
In order to understand the above sum,
set $w=x-y$,  so
$$
  \sum_{k=-n} ^n e ^{2 \pi ik(x-y)} =
  \sum _{k=-n}^{n}e^{2\pi ikw} =  $$$$ =
  \frac{e^{-2\pi inw}-e^{2\pi inw}}{1-e^{2\pi iw}}  =
  {\frac {\sin \left(\left(2n+1\right)\pi w\right)}{\sin(\pi w)}}.
  $$
The function
$$
  D_n(w) =   {\frac {\sin \left(\left(2n+1\right)\pi w\right)}{\sin(\pi w)}}
  $$
is called the Dirichlet kernel and we have thus concluded that
$$
  S_nf(x)=
  \int_{-\frac{1}{2}}^{\frac{1}{2}}  D_n(x-y)f(y)\, dy.
  \tag 1
  $$
From this it follows that  $\|S_n\|$ coincides with the 1-norm
$$
  \|D_n\|_1 = \int_{-\frac{1}{2}}^{\frac{1}{2}} |D_n(w)|\, dw
  $$
of the Dirichlet kernel which is known to converge to infinity roughly as fast as $\log(n)$.  Thus the $S_n$ are unbounded.
QED

Alternative Proof of same Theorem.
Another proof, a bit more abstract, is as follows:  assume by contradiction that the $S_n$ are bounded.  Observing
moreover that

$S_nf$ converges to $f$ for every trigonometric polynomial $f$,

the trigonometric polynomials are dense in the subspace of $C([-1/2, 1/2])$ formed by the periodic functions,

we would be able to conclude that   $S_nf$ converges to $f$ for every continuos periodic function on $[-1/2, 1/2]$,
but this is known to be false, leading to a contradiction, so  the $S_n$ are unbounded.  QED

Addressing the norm of the functional
$T_nf:= S_nf(0)$,
observe that if $f$ is periodic,  then by extending $f$ to a periodic function on $\mathbb R$,  one has by (1)  that
$$
  S_nf(x-x_0)=
  \int_{-\frac{1}{2}}^{\frac{1}{2}}  D_n(x-x_0-y)f(y)\, dy = $$$$ =
  \int_{x_0-\frac{1}{2}}^{x_0+\frac{1}{2}}  D_n(x-y)f(y-x_0)\, dy = $$$$ =
  \int_{-\frac{1}{2}}^{\frac{1}{2}}  D_n(x-y)f(y-x_0)\, dy =
  S_n(\tau_{x_0}f)(x),
  $$
where  $\tau_{x_0}f(x) = f(x-x_0)$.  Plugging in $x=0$, and $x_0=-x$, we get
$$
  S_nf(x)=   S_n(\tau_{-x}f)(0) = T_n(\tau_{-x}f).
  $$

This said, we see that
$$
  \|S_nf\| =
   \sup_x |S_nf(x)|=
   \sup_x |T_n(\tau_{-x}f)| \leq
   \sup_x \|T_n\|\|\tau_{-x}f\| =
   \|T_n\|\|f\|,
  $$
so we see that $\|S_n\|\leq \|T_n\|$.  Since we know that $\|S_n\|$ is unbounded, it follows that $\|T_n\|$ is also unbounded.


问:
Prove the norm property of random variables
Let $X$ is a random variable. Then prove this inequality.
$$
\|X\|_{L^2} \leq \|X\|_{L^1}^{\frac{1}{4}}\|X\|_{L^3}^{\frac{3}{4}}
$$

I think maybe using Caushy-Schwarz is effective but was stucked on this proposition.
I'll give a great appropriciate you!

答:
Write
$X^2=\lvert X\rvert^{1/2}\lvert X\rvert^{3/2}$ and apply Cauchy-Schwarz inequality in order to bound $\mathbb E\left[X^2\right]$. Then rearrange everything in terms of norms.


问:
Congruence with powers and primitive roots
Determine all the solutions of the congruence

$x^{85} ≡ 25 \pmod{31}$

using index function in base $3$ module $31$.

It is clear to me that $3$ is primitive root module $31$, but how do I use this information in the solution?

答:
Using Discrete logarithm  with respect to base $3$,

$85\cdot$ind$_3x\equiv2\cdot$ind$_35\pmod{30}$

As $85\equiv-5\pmod{30},$

$-5\cdot$ind$_3x\equiv2\cdot$ind$_35\pmod{30}\ \ \ \ (1)$

$3^3\equiv-4,3^5\equiv9\cdot(-4)\equiv-5\pmod{31}$

As $3$ is a primitive root $\pmod{31}, -1\equiv3^{30/2}\pmod{31}$

$\implies5\equiv3^{15}\cdot3^5\pmod{31}$

By $(1), -5\cdot$ind$_3x\equiv2\cdot20\pmod{30}\equiv-20$

Dividing  through out by $-5$

ind$_3x\equiv4\pmod6$

$\implies x\equiv3^{4+6k}\pmod{31}$  where $0\le4+6k\le30\iff0\le k\le4$


问:
A $1-1$ function is called injective. What is an $n-1$ function called?
A $1-1$ function is called injective. What is an $n-1$ function called ?

I'm thinking about homomorphisms. So perhaps homojective ?

Onto is surjective. $1-1$ and onto is bijective.

What about n-1 and onto ? Projective ? Polyjective ?

I think $n-m$ and onto should be hyperjective as in hypergroups.

答: n-1 + onto is sometimes called n-fold cover (by analogy).</p>

ContentLicense: CC BY-SA 3.0

ContentLicense: CC BY-SA 2.5


问:
Cooperative Game Theory specialized forum
I am looking for research-focused Game Theory forum, especially in Cooperative Game Theory. As it sometimes happen google provides links on either conferences (as opposed to online forums) or forums where students make their homework.
Could anyone suggest one?</p>

答: The following sites/blogs while not confined to cooperative game theory have lots of pointers to recent papers and conferences that deal with the rapidly evolving new results in game theory (and mechanism design and mathematical economics): (Center For Rationality at Hebrew University) http://www.ratio.huji.ac.il/dp.php  (A blog run by Noam Nissan) http://agtb.wordpress.com/  (blog run by Alvin Roth) http://marketdesigner.blogspot.com/ </p>


问:
Factorizing expression with exponents
I fail to see the justification that allows the textbook author to go from line 2 to line 3.
$$ C_1 e ^{u} - C_1 e^{-u} = 0$$
$$ C_1 (e^{u} - e^{-u}) = 0 $$
 $$C_1 (e^{2u} - 1) = 0$$
where $u = \sqrt{-\lambda} L$.</p>

Title: Factorizing expression with exponents

Body: $C_1(e^u - e^{-u}) \\ = C_1e^{-u}(e^{2u}-1) = 0 \\= C_1 (e^{2u} - 1) = 0 \, \\\blacksquare $


问:
There's an arrangement of vectors in linear space V over the field K. Is it possible that the field $lin(A)$ is infinitely dimensional?

Let's take $A = \{α_1, α_2, ...\}$ as an arrangement of vectors in linear space V over the field K. Suppose that dim $lin \{α_i, α_{i+1}, α_{i+2}\} = 2$ for each $i \geq 1$. Is it possible that the field $lin(A)$ is infinitely dimensional?

Vectors $A = \{α_1, α_2, ...\}$ can be seen as a matrix of $2$ linearly independent columns for every $3$ in a row. This can be visualised as:
$$A=\pmatrix{ind&ind&dep&ind&ind&dep&...\\ ind&ind&dep&ind&ind&dep&... \\ ind&ind&dep&ind&ind&dep&...\\ ind&ind&dep&ind&ind&dep&... \\ ...&...&...&...&...&... &...}$$

Then it possible that the field $lin(A)$ is infinitely dimensional.

Can somebody tell me if I think correctly?

答:
It depends on whether many of the $\alpha_i$ can be zero.  If infinitely many can be zero, you can have at least one in every three zero and the condition will hold.  If infinitely many are not zero you can have an infinite dimensional space.
If zero vectors are excluded you cannot have an infinite dimensional space.  We are told that we can write $\alpha_3$ as a comibination of $\alpha_1$ and $\alpha_2$.  Then we can write $\alpha_4$ as a combination of $\alpha_2$ and $\alpha_3$.  What does that tell you?  Continue


问:
Finite Content with Atomfreeness on Infinite Algebra
For an algebra $\mathcal{A}$ (not necessarily a $\sigma$-Algebra) over $X =[0,1]$ we define a finite content to be a function $\mu \colon \mathcal{A} \rightarrow [0,a]$ for some $a \in \mathbb{R}^{>0}$ with

$\mu(\emptyset) = 0$, $\mu(X) = a$ and

for all $A, B \in \mathcal{A}$ it holds that $\mu(A \cup B) = \mu(A) + \mu(B) - \mu(A \cap B)$.

Furthermore, $\mu$ is said to be atom-free, if for all $x \in X$ it holds that $\mu(\{x\}) = 0$.

Obviously, the power set $\mathcal{P}(X)$ is an algebra over $X$. Given these definitions, I am wondering whether there is any formal argument why either

there is no finite, atom-free content $\nu \colon \mathcal{P}(X) \rightarrow [0,1]$ or

why one cannot write down such a content $\nu \colon \mathcal{P}(X) \rightarrow [0,1]$ explicitly in a finite amount of space?

Note that I do not demand $\nu$ to satisfy translation invariance.

答:
Given an infinite set $X$, we can pick an arbitrary free ultrafilter $\mathcal F$ on $X$ and define a required content putting for each subset $A$ of $X$ put $\mu(A)=a$, if $A\in\mathcal F$, and $\mu(A)=0$, otherwise.

I think whether the required content can be “constructed” explicitly is a hard question. A similar question for countable $X$ was considered at MO. According to Stefan Geschke

In ZF you can't prove that there is a finitely additive measure on $\mathcal P(\mathbb N)$ (giving all singletons measure 0 and $\mathbb N$ measure 1). The existence of such a measure gives you a subset of $\mathbb R$ without the Baire property, and such a set cannot be constructed without some help of the axiom of choice. In other words, there is no explicit "construction" of a non-trivial finitely additive measure.

I guess the same conclusion holds for your question, but I am to weak in set theory to provide less vague and more rigorous claims.


答:
Yes: if $A$ is a real matrix, then it is Hermitian if and only if it is symmetric.

Similarly, if $U$ is a real matrix, then it is unitary if and only if it is orthogonal. With that said, it is indeed true that a real symmetric matrix is unitarily diagonalizable. The spectral theorem for symmetric matrices that $A$ is orthogonally diagonalizable, i.e. there exists a real diagonal matrix $D$ and an orthogonal matrix $U$ for which $A = UDU^{-1}$. Since $U$ is real and orthogonal, it follows that $U$ is unitary, which means that $A$ is also unitarily diagonalizable.

Title: Symmetric matrix and Hermitian matrix, unitarily diagonalizable

Body:
If $A$ is an n by n real matrix, then $A$ is Hermitian if and only if $A$ is symmetric.

Is this statement true or false? I think it is true?

Second question: Is every real symmetric matrix unitarily diagonalizable?
This is false right?   I want see some explanation, thank you.


问:
Is this stopping time finite a.s ? bounded?
Let $B$ and $W$ be two independent Brownian motions on $(\mathcal{F}_{t})$. Is $\tau$ defined as:
$$\tau = \inf \{ t \ge 0: B_{t} \ge W_{t} + e^{-t} \}$$ almost surely finite ? Bounded ?

I would say that it can not be finite due to Brownian motion and therefore can't be bounded. But I don't know how to prove it.
What do you think guys ?

答:
The proof in the other answer shows that $\tau$ is not bounded, but we actually do have that $\tau < \infty$ almost surely.  To show that, first note that by Levy's characterization of Brownian motion, $\hat B_t := \frac{1}{\sqrt 2} (B_t - W_t)$ is a Brownian motion.  Then $\tau = \inf\{ t : B_t \ge W_t + e^{-t} \} = \inf\{ t : \hat B_t \ge \frac{1}{\sqrt 2} e^{-t}\}$, so we have

\begin{align*}
P(\tau = \infty) &= P(\hat B_t < \frac{1}{\sqrt{2}} e^{-t} \text{ for all }t \ge 0) \\
&\le P(\hat B_t < \frac{1}{\sqrt{2}} \text{ for all }t \ge 0).
\end{align*}

By the recurrence property of Brownian motion, this final probability is $0$.


答: If $G$ is a simple graph with five vertices, say $v_1,v_2,v_3,v_4,v_5$, and nine edges, then it has all edges except $v_iv_j$ for some values $i,j$. $H$ is isomorphic to $G$ because you can map $c$ to $v_i$, $e$ to $v_j$, and $a,b,d$ to the other three vertices in some order.

Title: Isomorphism of All Simple Graphs with 5 Vertices and 9 Edges

Body:
Given the simple graph H with vertex set {a,b,c,d,e} and nine edges consisting of all possible edges except edge {c,e}. Are all simple graphs with five vertices and nine edges isomorphic to H? Why?

I tried solving this by checking every permutation and I think the answer is yes, but my question really is, how can we explain or prove this?


问:
I am not getting this in binomial?
No ways to arrange ABC by using C(3,2) is AB BC AC . Not BA CB OR CA including.

When we solve $(a+b)^2$

a^2 + b^2 + 2ab

Is it that no ways to arrange for the 3rd term since it would be C(2,1) . it is no ways to arrange them would be ab or ba.
How do we write this here then?

答:
In light of your addition edit here is a second answer:

It is misleading and unfortunate that the text used "arrangement".  I believe a better (albeit semantically confusing and challenging) way of saying it would be "choices to position 2 out 3 items".

The coefficient of the $ab^2$ term in $(a+b)^3$ is ${3\choose 2} = 3$ is not because we are arranging $2$ out of three different objects, but instead it is because we are choosing out of $3$ copies of $b$ we are picking $2$ of them.

.....

Bear with me.

When we have $(a+b)^k$ we have $k$ copies of the pair $a,b$.  (I'll illustrate with color)

$$(a+b)^k = \color{blue}{(a+b)}\color{red}{(a+b)}\color{green}{(a+b)}\color{orange}{(a+b)}$$

When we expand that out we will pick one $a$ or $b$ from each pair to get $2^k$ terms:

$$ \color{blue}{(a+b)}\color{red}{(a+b)}\color{green}{(a+b)}\color{orange}{(a+b)}=\\ \color{blue}a\color{red}a\color{green}a\color{orange}a+\color{blue}a\color{red}a\color{green}a\color{orange}b+\color{blue}a\color{red}a\color{green}b\color{orange}a+\color{blue}a\color{red}a\color{green}b\color{orange}b+\\ \color{blue}a\color{red}b\color{green}a\color{orange}a+\color{blue}a\color{red}b\color{green}a\color{orange}b+\color{blue}a\color{red}b\color{green}b\color{orange}a+\color{blue}a\color{red}b\color{green}b\color{orange}b+\\ \color{blue}b\color{red}a\color{green}a\color{orange}a+\color{blue}b\color{red}a\color{green}a\color{orange}b+\color{blue}b\color{red}a\color{green}b\color{orange}a+\color{blue}b\color{red}a\color{green}b\color{orange}b+\\ \color{blue}b\color{red}b\color{green}a\color{orange}a+\color{blue}b\color{red}b\color{green}a\color{orange}b+\color{blue}b\color{red}b\color{green}b\color{orange}a+\color{blue}b\color{red}b\color{green}b\color{orange}b$$

Now as a term with $m$ $b$s (and the remaining $k-m$ all being $a$s) are all the same and it doesn't matter which of the $k$ choices the $m$ $b$s came from we can combine then.

So the coefficient of the $a^{k-m}b^m$ will be the number of ways that, out of $k$ total copies of our $b$s, we can chose $m$ of them.

Let's draw a picture (For the picture I'll have to acknowledge I'm using $k = 4$).

$$\color{blue}a\color{red}a\color{green}a\color{orange}a+\color{blue}a\color{red}a\color{green}a\color{orange}b+\color{blue}a\color{red}a\color{green}b\color{orange}a+\color{blue}a\color{red}a\color{green}b\color{orange}b+\\ \color{blue}a\color{red}b\color{green}a\color{orange}a+\color{blue}a\color{red}b\color{green}a\color{orange}b+\color{blue}a\color{red}b\color{green}b\color{orange}a+\color{blue}a\color{red}b\color{green}b\color{orange}b+\\ \color{blue}b\color{red}a\color{green}a\color{orange}a+\color{blue}b\color{red}a\color{green}a\color{orange}b+\color{blue}b\color{red}a\color{green}b\color{orange}a+\color{blue}b\color{red}a\color{green}b\color{orange}b+\\ \color{blue}b\color{red}b\color{green}a\color{orange}a+\color{blue}b\color{red}b\color{green}a\color{orange}b+\color{blue}b\color{red}b\color{green}b\color{orange}a+\color{blue}b\color{red}b\color{green}b\color{orange}b=$$

[Ways to have $0$ $b$s:]  $\color{blue}a\color{red}a\color{green}a\color{orange}a+$  [(${4\choose 0}=1$ ways to do it]

[Ways to have $1$ $b$:]  $\color{blue}a\color{red}a\color{green}a\color{orange}b+\color{blue}a\color{red}a\color{green}b\color{orange}a+\color{blue}a\color{red}b\color{green}a\color{orange}a+\color{blue}b\color{red}a\color{green}a\color{orange}a+$ [(${4\choose 1}=4$ ways to do it]

[Ways to have $2$ $b$s:]  $\color{blue}a\color{red}a\color{green}b\color{orange}b+\color{blue}a\color{red}b\color{green}a\color{orange}b+\color{blue}a\color{red}b\color{green}b\color{orange}a+\color{blue}b\color{red}a\color{green}a\color{orange}b+\color{blue}b\color{red}a\color{green}b\color{orange}a+\color{blue}b\color{red}b\color{green}a\color{orange}a+$ [(${4\choose 2}=6$ ways to do it]

[Ways to have $3$ $b$s:]  $\color{blue}a\color{red}b\color{green}b\color{orange}b+\color{blue}b\color{red}a\color{green}b\color{orange}b+\color{blue}b\color{red}b\color{green}a\color{orange}b+\color{blue}b\color{red}b\color{green}b\color{orange}a+$ [(${4\choose 3}=4$ ways to do it]

[Ways to have $4$ $b$s:]  $\color{blue}b\color{red}b\color{green}b\color{orange}b=$  [(${4\choose 4}=1$ ways to do it]

$${4\choose 0}a^4 + {4\choose 1}a^3b + {4\choose 2}a^2b^2 + {4\choose 1}a^3b + {4\choose 0}b^4=\\ a^4 + 4a^3b+ 6a^2b^2 + 4ab^3 +b^4$$.

And that's the binomial theorem!

......

so $$(a+b)^2 =\\\color{blue}{(a+b)}\color{red}{(a+b)}=\\\color{blue}a\color{red}a+\color{blue}a\color{red}b+\color{blue}b\color{red}a+\color{blue}b\color{red}b=\\\color{blue}a\color{red}a + \color{blue}b\color{red}b + (\color{blue}a\color{red}b+\color{blue}b\color{red}a)=\\a^2 + b^2 + 2ab$$

====

P.S.  Neat little fact that comes out of all this meshugana is that ${n\choose 0} + {n\choose 1} + {n\choose 2} + ....... +{n\choose n-1} + {n\choose n} = 2^n$.

Who would have thunk it?!

Title: I am not getting this in binomial?


问:
Finite field extension and roots of a polynomial of degree 3
Let $L/K$ be a finite field extension with $[L:K] = 2^k$ and $f \in K[X]$ be a polynomial of degree 3 that has a root in $L$. Show that $f$ has a root in $K$.

I was thinking about proving this with induction but I have trouble with the base case:

$k=1$: Without loss of generality we can assume that $f$ is monic, so $f = X^3 + aX^2 + bX + c$. Then $[L:K] = 2$ and since $2$ is prime, there exists an $\alpha \in L$ such that $L = K(\alpha)$. Now the Minimal polynomial $g$ of $\alpha$ over $K$ is of degree 2 and since it is also monic, it must be a divider of $f$ (I'm not sure about this one). So $f = g\cdot h$ with $\deg(h) = 1$. Since $h$ is a linear polynomial over $K$ it must have a root in $K$.

I'm not sure if this was correct since I didn't really need that $f$ has a root in $L$? Any hints would be greatly appreciated.

答: If $f$ has no solution over $K$ and a root $a$ in $L$, then $f$ is irreducible in $K$ and $L$ contains a subfield $K(a)$ isomorphic to $K[X]/(f)$. Such a field has degree $3$ and cannot be contained in $L$, since $3$ doesn't divide $[L:K]$


问:
How do I find the residuals of this problem?

Find all the singularities in the finite plane and the corresponding residues. Show the details.

$$\frac{8}{1+z^2}$$

I am a bit stuck on this problem:

So I know the residual is going to be the coefficient associated with the first negative exponent in the Laurent series. Why do I have to find both the singularities and the residual? They seem like different questions no?

So the singularities are at $z = i$ because $i^2 = -i$ and that's when the denominator will equal 0.

But how do I find the residuals? So I remember that:

$$\frac{1}{1+z} = 1 - z + z^2 - ...$$

So I now multiply each element by 8:

$$\frac{8}{1+z} = 8(1 - z + z^2 - ...)t$$

But none of these terms have an exponent of -1 so I cannot find the coefficient...

Sigh, what am. I doing wrong?

Next problem, same as above but different function: $$\frac{1}{1-e^z}$$

答:
$f(z)=\frac{8}{z^2+1}$ has simple poles at $z=\pm i$
$$\text{Res}(f(z),i)=\underset{z\to i}{\text{lim}}\frac{8 (z-i)}{(z-1) (z+i)}=\frac{8}{2i}=-4i$$
in a similar way can be proved that
$$\text{Res}(f(z),-i)=4i$$

Forgot the second question
$$\frac{z}{1-e^z}=-1+\frac{z}{2}-\frac{z^2}{12}+O\left(z^3\right)$$
the dividing by $z$ we get
$$g(z)=\frac{1}{1-e^z}=-\frac{1}{z}+\frac{1}{2}-\frac{z}{12}+O\left(z^2\right)$$
Therefore
$$\text{Res}(g(z),0)=-1$$


问:
Compute integral $\int_{-\infty}^\infty \frac{x^4}{1+x^8} \, dx$
Compute the integral.

$$\int_{-\infty}^\infty \frac{x^4}{1+x^8} \, dx$$

The answer at the back of the book is
$$\frac{\pi}{4\sin(\frac{3\pi}{8})}$$

答:
Note

\begin{align}
\int_{-\infty}^\infty \frac{x^4}{1+x^8} dx
& =-\frac1{2i}\int_{-\infty}^\infty \left(\frac{1}{1+i x^4} - \frac{1}{1-i x^4} \right)dx \\
& = -\text{Im} \int_{-\infty}^\infty \frac{1}{1+i x^4}dx
\overset{t=i^{1/4}x} =  -\text{Im} \left( e^{-i\frac\pi8}\int_{-\infty}^\infty \frac{1}{1+t^4}dt\right)\\
&=   -\text{Im} \left( e^{-i\frac\pi8}\cdot \frac\pi{\sqrt2} \right)= \frac\pi{\sqrt2}\cdot\sin\frac\pi8= \frac\pi2\sqrt{1-\frac1{\sqrt2}}
\end{align}


问:
A boundary version of Cauchy's theorem
I am looking for a reference for the following theorem (or something like it) that is not Kodaira's book.

Let $D$ be a domain and $\overline{D}$ be it's closure. Suppose that $f:\overline{D} \rightarrow \mathbb{C}$ is holomorphic in $D$ and continuous on $\overline{D}$. If the boundary of $D$, denoted $\partial D$ is composed of piecewise $C^1$ curves then
    $$f(w) = \frac{1}{2\pi i}\oint_{\partial D}\frac{f(z)}{z-w}dz$$
    for all $w\in D$.

This is stronger than the classical Cauchy integral theorem, because here we can allow the path we integrate over to be the boundary. This appears in Kodaira's book, but the book seems sloppily written and I found an egregious error in the first few pages, so I'd like another reference.

This does not appear in Ahlfors or any other standard text I looked at. I am looking for any proof that extends to usual Cauchy's theorem to allow paths that lie on the boundary of a region, instead of requiring them to lie entirely in the open region like the usual version does.

I managed to find a paper that sketches a high-powered proof when the boundary is a rectifiable Jordan arc (or some multiply connected region where each boundary component is) and gives a reference to a more elementary proof of the same result. I think a simpler proof should be possible in this case, where the boundary is assumed to be $C^1$.

This is closely related to an old question that did not get much attention.

答:
My apologies on my misreading the first time. Knowing $f$ is continuous on $\overline D$, for $\delta>0$ with $|w|<1-\delta$, we will know that the Cauchy integrand
$$\frac{f(z)}{z-w}$$
is uniformly continuous on $\{z: 1-\delta\le z\le 1\}$, and so the integral over the circle of radius $1-\delta$ converges to the integral over $\partial D$.</p>

Title: A boundary version of Cauchy's theorem


问:
Evaluate $\lim_ {n \to\infty} n (n^ {\frac {1} {n}}-2^ {\frac {1} {n}}) ^a$ as $a$ varies in the reals
How would you evaluate $\lim_ {n \to\infty} n (n^ {\frac {1} {n}}-2^ {\frac {1} {n}}) ^a$ with $n$ an integer and $a$ a real parameter? I tried to apply the most common criteria and to compare this with some other easier functions but without success.
Thank you

答:
If $a\le 0$
$$n\left( n^\frac 1n - 2^\frac 1n\right)^a = \frac{n}{\left(n^\frac 1n - 2^\frac 1n\right)^{|a|}} > \frac{n}{\left(n^\frac 1n \right)^{|a|}} = n^{1-\frac 1n |a|} \to \infty$$

If $a>0$
$$n^\frac 1n = e^{\frac 1n \ln n} = 1+ \frac 1n \ln n+O\left(\frac{\ln^2 n}{n^2}\right)$$
$$2^\frac 1n = e^{\frac 1n \ln 2} = 1+ \frac 1n \ln 2+O\left(\frac{1}{n^2}\right)= 1+ \frac 1n \ln 2+O\left(\frac{\ln^2 n}{n^2}\right)$$

Since $\frac 1n$ dominates $\frac{\ln^2 n}{n^2}$, we have
$$n^\frac 1n - 2^\frac 1n=\frac 1n \ln n-\frac 1n \ln 2+O\left(\frac{\ln^2 n}{n^2}\right) > \frac{\ln n}{2n}, \text{ when } n \text{ is large} \tag 1$$

And
$$n^\frac 1n - 2^\frac 1n=\frac 1n \ln n-\frac 1n \ln 2+O\left(\frac{\ln^2 n}{n^2}\right) < \frac 1n \ln n \text{, when } n \text{ is large }\tag 2$$

Now if $a>1$,
$$\text{when } n \text{ is large, } n\left( n^\frac 1n - 2^\frac 1n\right)^a < \frac{(\ln n)^a}{n^{a-1}} \to 0 \text{ via L'Hôpital}$$

If $0 < a \le 1$
$$\text{when } n \text{ is large, } n\left( n^\frac 1n - 2^\frac 1n\right)^a > \frac{n^{1-a} (\ln n)^a}{2^a} \to \infty $$

Conclusion: The limit is $\infty$ if $a\le 1$, $0$ if $a>1$.


答:
Let $V$ be the vector space of real sequences $(a_n)_{n=0}^{\infty}$. Let $e_j$ denote the sequence which has $1$ in the $j$-th place and $0$ elsewhere. Let $f_j=e_j$ when $j\not= 0\mod 3$, and let $f_{3k}=0$.

Then the vectors $f_0, f_1, f_2, \dots$ satisfy the required condition and span an infinite dimensional space.

Title: There's an arrangement of vectors in linear space V over the field K. Is it possible that the field $lin(A)$ is infinitely dimensional?

Body:
Let's take $A = \{α_1, α_2, ...\}$ as an arrangement of vectors in linear space V over the field K. Suppose that dim $lin \{α_i, α_{i+1}, α_{i+2}\} = 2$ for each $i \geq 1$. Is it possible that the field $lin(A)$ is infinitely dimensional?

Vectors $A = \{α_1, α_2, ...\}$ can be seen as a matrix of $2$ linearly independent columns for every $3$ in a row. This can be visualised as:
$$A=\pmatrix{ind&ind&dep&ind&ind&dep&...\\ ind&ind&dep&ind&ind&dep&... \\ ind&ind&dep&ind&ind&dep&...\\ ind&ind&dep&ind&ind&dep&... \\ ...&...&...&...&...&... &...}$$

Then it possible that the field $lin(A)$ is infinitely dimensional.

Can somebody tell me if I think correctly?


答:
You can write the following:
$$\frac{8}{1+z^2}=\frac{8}{(z-i)(z+i)}$$
So we have two simple poles, one at $z=i$ and another at $z=-i$. We can then use the following:
$$\text{Res}(f,c)=\lim_{z\rightarrow c}(z-c)f(z)$$
Which gives:
$$\text{Res}(f,i)=\lim_{z\rightarrow i}\frac{8}{z+i}=-4i$$
Similarly we obtain:
$$\text{Res}(f,-i)=4i$$
For $f(z)=\frac{1}{1-e^z}$ we rewrite $e^z$ using eulers formula and obtain:
$$f(z)=\frac{1}{1-e^x(\cos(y)+i\sin(y))}$$
Clearly we have simple poles when $z=2\pi in$ for all $n\in\mathbb{Z}$, and everywhere else the function is well behaved. Taking the limit as before we find:
$$\text{Res}(f,2\pi i n)=\lim_{z\rightarrow 2\pi in}\frac{x+iy-2\pi in}{1-e^x(\cos(y)-i\sin(y)}$$
Setting $x=0$ we obtain:
$$\lim_{y\rightarrow 2\pi n}\frac{iy-2\pi i n}{1-\cos(y)-i\sin(y)}=\lim_{y\rightarrow 2\pi n}\frac{i}{\sin(y)-i\cos(y)}=-1$$
Thus we have that $f(z)$ has simple poles at $z=2\pi i n$ with residues of $-1$.

Note: For higher order poles, you must either look at the laurent series expansion or use the following formula for an $n$th order pole:
$$\text{Res}(f,c)=\frac{1}{(n-1)!}\lim_{z\rightarrow c}\frac{d^{n-1}}{dz^{n-1}}[(z-c)^nf(z)]$$

Title: How do I find the residuals of this problem?

Body:
Find all the singularities in the finite plane and the corresponding residues. Show the details.

$$\frac{8}{1+z^2}$$

I am a bit stuck on this problem:

So I know the residual is going to be the coefficient associated with the first negative exponent in the Laurent series. Why do I have to find both the singularities and the residual? They seem like different questions no?

So the singularities are at $z = i$ because $i^2 = -i$ and that's when the denominator will equal 0.

But how do I find the residuals? So I remember that:

$$\frac{1}{1+z} = 1 - z + z^2 - ...$$

So I now multiply each element by 8:

$$\frac{8}{1+z} = 8(1 - z + z^2 - ...)t$$

But none of these terms have an exponent of -1 so I cannot find the coefficient...

Sigh, what am. I doing wrong?

Next problem, same as above but different function: $$\frac{1}{1-e^z}$$


问:
Prove $x_n=\frac{n}{2^n}$ converges to $0$
Prove $x_n=\frac{n}{2^n}$ converges to $0$.

Since $2^n>\frac{n^2}{2}$ for all $n \in \mathbb{N}$ we have

$$-\frac{2}{n}<\frac{n}{2^n}<\frac{2}{n}.$$

Since $\frac{1}{n} \rightarrow0$ as $n \rightarrow \infty$, by Squeeze theoreom $\frac{n}{2^n}$ converges to $0$.

Is there anything wrong this proof?

答:
$$\frac n{2^n}=\frac12\frac2{1\cdot2}\frac3{2\cdot2}\frac4{3\cdot2}\frac5{4\cdot2}\cdots\frac{n-1}{(n-2)2}\frac n{(n-1)2}
\\<\frac12\frac2{1\cdot2}\frac3{2\cdot2}\frac3{2\cdot2}\frac3{2\cdot2}\cdots\frac3{2\cdot2}\frac3{2\cdot2}\to0$$

Possibly more obvious:

$$n=1\frac21\frac32\frac43\frac54\cdots\frac{n-1}{n-2}\frac n{n-1}<1\frac21\frac32\frac32\frac32\cdots\frac32\frac32=2\left(\frac32\right)^{n-2}.$$

And of course

$$\frac n{2^n}<\frac12\left(\frac34\right)^{n-2}.$$


问:
$\eta$ - strongly convex functions definition
I'm trying to understand better the following definition:

"A function $f:\mathbb{R}^d \rightarrow \mathbb{R}$ is $\eta$ - strongly convex with $\eta > 0$ if for all $\alpha, p \in \mathbb{R}^d$ then

$$f(p) \le f(\alpha) + \langle\nabla f(\alpha),p-\alpha\rangle + \frac{\eta}{2}\|p-\alpha\|^2."$$

"Intuitively, we have that $f$ is at least quadratic (why?), that is along any direction $u = \frac{p-\alpha}{\|p-\alpha\|}$ the function $\langle f , u \rangle$ is 1-dimensional  and its second derivative is strictly positive. Which is the connection for $f$ being at least quadratic? Thank you.

EDIT:

the inequality is exactly like that. I took this result from the book "Mathematical foundations for Data Analysis" By Jeff Philips found here.

https://www.cs.utah.edu/~jeffp/M4D/M4D-v0.4.pdf

答:
Intuitively, we can think of Lipschitz-smoothness and strong convexity as duals to one another (for many reasons, convex conjugation is one good one but I will explore a different one here). A convex differentiable function $f$ is Lipschitz-smooth with constant $L>0$ iff, for any $x,y$ it holds,

$$f(y) - f(x) - \langle\nabla f(x), y-x\rangle \leq \frac{L}{2}\|x-y\|^2.$$

Meanwhile, a convex function $f$ is strongly convex with constant $\eta>0$ iff, for any $x,y$ it holds,

$$f(y) - f(x) - \langle\nabla f(x), y-x\rangle \geq \frac{\eta}{2}\|x-y\|^2.$$

So what's really going on? Lipschitz-smoothness corresponds to a quadratic upper bound and strong convexity corresponds to a quadratic lower bound. In fact, these inequalities can both be derived from the convexity of the difference functions,

$$g_1(x) = f(x) - \frac{1}{2}\|x\|^2\quad\mbox{and}\quad g_2(x) = \frac{1}{2}\|x\|^2 - f(x)$$

When $g_1$ is convex for all $x$, the function $f$ is strongly convex. When $g_2$ is convex for all $x$, the function $f$ is Lipschitz-smooth. You can introduce constants $L$ and $\eta$ here as well.

Unrelated to your question, but if you know about Bregman divergences then this whole thing can be rewritten. Let $D_f(x,y)$ be the Bregman divergence associated to $f$. Then, we can say that $f$ is relatively smooth with respect to $F$ iff $\exists L>0$ such that, for any $x,y$,

$$D_f(x,y) \leq L D_F(x,y)$$

and similarly, $f$ is relatively strongly convex with respect to $F$ iff $\exists \eta > 0$ such that, for any $x,y$,

$$D_f(x,y) \geq \eta D_F(x,y).$$

So smoothness and strong convexity are really describing the domination of $D_f$ by another Bregman divergence $D_F$. We can recover Lipschitz-smoothness and strong convexity by taking $F(x) = \frac{1}{2}\|x\|^2$ but we are free to explore alternatives!


问:
Prove $n \cdot x = n * x$ in $\mathbb{R}$
In general, if $(R, +, *)$ is a ring, then for all $i, j \in \mathbb{Z}$ and $r \in R$,
$$(i \cdot r) * (j \cdot r) = (ij)*r \text,$$
where $i \cdot r$ denotes the $i$th power of $r$ as an element of $(R, +)$. A product of sums is a sum of products.

If the ring is $\mathbb{R}$, then there is an additional property that
$$i \cdot r = i * r \text.$$
This makes sense: multiplication is iterated addition. $4 \cdot 3 = 3 + 3 + 3 + 3 = 4 * 3$. What is a rigorous proof of this property?

I expect this proof will require some construction of the real numbers; I don't have a preference for any particular construction. Or maybe this is true for any field.

答:
I think this is an interesting question, and the Q&A here goes a long way to understanding it: In a ring, result of multiple (of "addition" operation) is not the same as result of multiplication, correct?

Essentially, for any ring with unity $(R, +_R, *)$ we can say that $$n\cdot x = n=\underbrace{x+_Rx+_R\cdots+_Rx}_{n\text{ times}}=  n*x$$ so long as we identify that $n$ on the RHS is defined as $n \cdot 1$. The reason this is necessary is because the expression $n*x$ is only meaningful if $n$ is an element of the (arbitrary) ring (and the natural number $n$ is not necessarily an element of said ring).

So certainly for the field $\mathbb{R}$, this will hold. To prove this then, we have to prove that a natural number $n$, is equal to $n \cdot 1$, where we are now working in the field $\mathbb{R}$.

But in some systems, by its very definition $2 = 1+1$. Particularly, using Peano axioms you can show using successor functions (and then assigning the symbols $1,2,..$ etc to these objects) that $n = n \cdot 1$ will hold for any natural number $n$. Thus the formula holds for any natural number $n$.


答:
Your proof is perfectly fine just that you don't need $\frac{-2}{n}$. You can just replace that by $0$.

Here's another alternative method by using the ratio test:

$\frac{x_{n+1}}{x_n}=\frac{\frac{n+1}{2^{n+1}}}{\frac{n}{2^n}}=\frac{1}{2}\left(\frac{n+1}{n}\right)$.

Now take the limit on both sides and thus, using the theorem of ratio test for sequences, if the limit $L$ exists and $0\leq L<1$ then $\text{lim }x_n=0$.

Body:
Prove $x_n=\frac{n}{2^n}$ converges to $0$.

Since $2^n>\frac{n^2}{2}$ for all $n \in \mathbb{N}$ we have

$$-\frac{2}{n}<\frac{n}{2^n}<\frac{2}{n}.$$

Since $\frac{1}{n} \rightarrow0$ as $n \rightarrow \infty$, by Squeeze theoreom $\frac{n}{2^n}$ converges to $0$.

Is there anything wrong this proof?


问:
Measure Theory Absolute Continuity
Qualifying Exam Practice.

Let $p>0$ and define $\nu(E) = \int_E x^p d \lambda(x)$, $E \in \mathcal{B}[1,\infty)$. Show that $\nu << \lambda$, but the limit $\lim_{\lambda(E) \rightarrow 0} |\nu(E)|$ is not zero.

I believe $\nu << \lambda$ can be shown using the absolute continuity of the Lebesgue integral. I am unclear about the second part.

答: The second part says that you can find sets $E$ with very small Lebesgue measure, yet such that the integral of $x^p$ over the set $E$ is not very small. So $E$ should be located someplace where $x^p$ is big. Try $E=[n,n+1]$ for large $n$.

Title: Measure Theory Absolute Continuity


问:
When is an Integer a Rational Number, and are All Ratios Rational, Even $\frac{\sqrt{7}}{2}$?

$$\Bbb{Q} = \left\{\frac ab \mid \text{$a$ and $b$ are integers and $b \ne 0$} \right\}$$

In other words, a rational number is a number that can be written as one integer over another.

For an integer, the denominator is $1$ in that case. For example, $5$ can be written as $\dfrac 51$.

Is $5$ a rational number? Or is $\dfrac 51$  a rational number? I'm not able to figure out what the definition is actually saying. What are the numbers that cannot be written as one integer over another?

Irrational numbers are the numbers that cannot be written as one integer over another. Roots of numbers that are not perfect squares are examples of irrational numbers.

However, what is this then: $\dfrac {\sqrt 7} {2}$?

答: Although there are many answers here already, unless if I have missed something none of them actually proves that $\sqrt{7}/2$ is irrational.  As already noted in the comments to amWhy's answer, it is not valid to say that if $a$ is not an integer then $a/b$ is irrational.  However, it is valid to say that if $a$ is irrational and $b$ is rational, then $a/b$ is irrational.  (This is because if $a/b$ and $b$ were both rational, then their product $a$ would be rational because the product of rational numbers is always rational.)  Because $\sqrt{7}$ is irrational (as shown in wece's answer) and 2 is rational, the ratio $\sqrt{7}/2$ is irrational.</p>


问:
Is there a stronger version of the Gluing Lemma?
The following is usually called "Gluing Lemma":

Given two measures $\gamma^+ \in \prod(\mu,\rho)$ and $\gamma^- \in \prod(\rho,\nu)$, there is at least one measure $\sigma\in \mathcal P(\Omega \times \Omega \times \Omega)$ such that $(\pi_{x,y})_\# \sigma = \gamma^+$ and $(\pi_{y,z})_\# \sigma = \gamma^-$,where $\pi_{x,y}$ and
$\pi_{y,z}$ denote the projections on the two first and two last variables, respectively.

Note that $\gamma^+ \in\prod(\mu,\rho)$  means that $\gamma ^+$ is a coupling of measures $\mu$ and $\rho$, in other words, the marginals of $\gamma^+$ are $\mu$ and $\rho$, respectively.

Now, I was wondering if there exists some sort of "Stronger Version" of the Gluing Lemma... In this original formulation, we need that both $\gamma^+$ and $\gamma^-$ to share the $\rho$ as marginal. But perhaps there are weaker conditions for the existance of such $\sigma$.

Here is an example of what I was looking for:

(Fictitious Lemma)
Given two measures $\gamma^+ \mathcal P(\Omega\times \Omega)$ and $\gamma^- \in \mathcal P(\Omega\times \Omega)$. If the support of $(\pi_y)_\#\gamma^+ = (\pi_y)_\#\gamma^-$ , then there is at least one measure $\sigma\in \mathcal P(\Omega \times \Omega \times \Omega)$ such that $(\pi_{x,y})_\# \sigma = \gamma^+$ and $(\pi_{y,z})_\# \sigma = \gamma^-$,where $\pi_{x,y}$ and
$\pi_{y,z}$ denote the projections on the two first and two last variables, respectively.

答: No, the condition $(\pi_y)_\#\gamma^+=(\pi_y)_\#\gamma^-$ is necessary: If you take the pushforward under $\pi_y$ of the identities $(\pi_{x,y})_\# \sigma = \gamma^+$ and $(\pi_{y,z})_\# \sigma = \gamma^-$, you get $(\pi_y\circ \pi_{x,y})_\#\sigma=(\pi_y)_\#\gamma^+$ and $(\pi_y\circ \pi_{y,z})_\#\sigma=(\pi_y)_\#\gamma^-$. But $\pi_y\circ\pi_{x,y}=\pi_y\circ\pi_{y,z}=\pi_y$, so that the two left sides coincide.


问:
Rank of incidence matrix of Hamming graph
Consider a Hamming graph $H(d, q)$.
What is the rank of its incidence matrix?

Hypergraph

A Hamming graph can be seen in two ways:

Take the numbers $0$ until $q^d - 1$ and represent them in base $q$. Each number is a vertex. Vertices are connected if exactly one base-$q$ digit is different.

Take $d$ complete graphs, each with $q$ vertices. The Hamming graph is the Cartesian product of these graphs.

I consider the Hamming graph to be a hypergraph, with each hyperedge connecting the $d$ vertices that differ in one digit given their base-$d$ representation.
As a result, the incidence matrix has $q$ 1s per column.
For example, for $H(2, 3)$, the incidence matrix would be
$$
\begin{bmatrix}
1 & 0 & 0 & 1 & 0 & 0 \\
1 & 0 & 0 & 0 & 1 & 0 \\
1 & 0 & 0 & 0 & 0 & 1 \\
0 & 1 & 0 & 1 & 0 & 0 \\
0 & 1 & 0 & 0 & 1 & 0 \\
0 & 1 & 0 & 0 & 0 & 1 \\
0 & 0 & 1 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 & 1 & 0 \\
0 & 0 & 1 & 0 & 0 & 1
\end{bmatrix}.
$$

q = 2

I found a proof (see Lemma 3) that the rank is $2^d - 1$ if $q = 2$.
Intuitively, this makes sense to me:
If you transpose the incidence matrix you get the $A$ in the system of linear equations $Ax = y$ for some $y$.
If you know just a single $x_i$ you can "chain" the solution to all other equations.
This means there is only a single free variable, so the rank is $2^d - 1$.

q > 2

But what happens when you change $q$?
I've constructed the general form of the incidence graph $G_{d, q}$ of $H(d, q)$:
$$
\begin{bmatrix}
G_{d - 1, q}  & 0             & \dots  & 0 \\
0             & G_{d - 1, q}  & \dots  & 0 \\
\vdots        & \vdots        & \ddots & \vdots \\
0             & 0             & \dots  & G_{d - 1, q} \\
I_{q^{d - 1}} & I_{q^{d - 1}} & \dots  & I_{q^{d - 1}}
\end{bmatrix}.
$$
Containing $q$ copies of $G_{d - 1, q}$, this is a $d q^{d - 1} \times q^d$ matrix

I wrote some code which varies the parameters $d$ and $q$, and extrapolating from those results I found the general formula $q^d - (q - 1)^d$.

Question

I want to use this formula in my thesis, and while I have an intuition as to why this formula might be correct, I find it difficult to give a proof of its correctness.
Despite my best efforts, I couldn't find any literature that confirm or contradict my results.

Another paper by W. Fish gives a general formula for the rank of the incidence matrix, but she uses regular edges instead of hyperedges, resulting in a different formula, $q^d - 1$, but this doesn't seem to be correct for my case based on the results of my code.

Could anyone point me to existing literature about this problem, or does someone know how to prove that my formula is correct?

答:
I was able to solve this problem in my master thesis, Privacy-Preserving Data Aggregation with Probabilistic Range Validation. It's in Theorem 6.4 in Section 6.2.2.

A few notes:

In my thesis I transposed the matrix w.r.t. my question above (i.e. each row is now a hyperedge). This does not affect the rank.

The proof is for hypermeshes, which are exactly the structure I described in my question. For more information, see Section 3 of the paper "Hypermeshes": Optical Interconnection Networks for Parallel Computing by Ted Szymanski.

The proof is for the incidence matrix of an irregular hypermesh, which you can see as the Hamming graph for a mixed-radix system. Observe that Theorem 6.4 matches the formula in my question if $b$ is a sequence of $d$ copies of $q$.

My proof uses complete induction, similar to the proof by W. Fish in the paper I linked in my question. The base case is a 1-dimensional hypermesh, which is trivial. The induction case involves a sequence of column operations such that the matrix is then in a column echelon form. I then count the number of empty columns to calculate the rank.


问:
Show that if the integral of a function from 0 to x is equal to the integral from x to 1, then f(x)=0
How can I prove that if $f$ is continuous on $[0, 1]$ such that for every $x \in [0, 1]$ we have that $\int_{0}^{x} f(t) \,dt = \int_{x}^{1} f(t) \,dt$, then $f(x)=0$ for every $x$.

Body: $$2\int_0^x f(x)\,dx=\int_0^x f(x)\,dx+\int_x^1 f(x)\,dx=\int_0^1 f(x)\,dx=\text{Cst}.$$


问:
The probability of getting 3 cards from the same kind from a piece of cards
Given 52 cards of $(1,2,3,..13)$ of $13$ cards from each shape, (4 shapes) what is the probability of
"get 3 cards of the same number and the other 2 cards are different from each other"

I was thinking of calculate it in the following way: $$ \frac{1}{13} \cdot \frac{1}{13} \cdot \frac{1}{13} \cdot \frac{1}{49} \cdot \frac{1}{48}$$

But this is not the current answer and I dont understand what is wrong in my attempt

答:
There are $\binom{52}{5}$ ways to choose the $5$ cards.  Three are $13$ ways to choose the rank of the three cards with the same rank and $\binom{4}{3}$ ways to choose $3$ cards of that rank.

Now for the two different cards, I take the question to mean that hey are also of different rank from the first three cards, so we have $\binom{12}{2}$ ways to choose the ranks of these cards, and $4$ ways to choose a card of each rank.

Finally, the probability is $$\frac{13\binom{4}{3}\binom{12}{2}4^2}{\binom{52}{5}}$$


问:
Proving a (little) statement involving the counting measure
Let $(X,\mathcal{P}(X),\#)$ where $X\neq \emptyset$. The counting measure is given by$$\mu : \mathcal{P}(X) \to [0,\infty], \, \mu(A)=\begin{cases}|A|  \, \,  \, \text{ if A is finite} \\ +\infty \text{ if A is infinte}\end{cases}$$

Statement:

Let $f: X\to \mathbb{R}$ be a measureable function is integratable with respect to $(X,\mathcal{P}(X),\#)$, iff there is at most a countable set $J\subseteq X$ with $f|_{X\setminus J}\equiv 0$ and $\sum _{j\in J}|f(j)|<\infty$

My idea:

"$\Rightarrow$"

I feel like this can easier proven when looking at the negated statement. So, let $f: X\to \mathbb{R}$ be measurable with respect to   $(X,\mathcal{P}(X),\#)$. Assume that there is at least one countable set  $J\subseteq X$ with $f|_{X\setminus J}\equiv 0$ and $\sum _{j\in J}|f(j)|<\infty$.

But I am getting nowhere, sadly. Does anyone have an idea on how to solve this? I feel like this isn't really that hard of a question which makes me even more furious.

答:
Notice that for any finite $J\subseteq X$, $\sum_{j\in J} \vert f(j)\vert$ is a simple function and is equal to its integral under the counting measure.

If $f\neq 0$ on an uncountable set, then by cardinality considerations, there exists some $k\in \mathbb{N}$ such that $\vert f(j)\vert\geq \frac{1}{k}$ for infinitely many $j$-s. This would contardict the integrability. Indeed one can write
$$\{ \vert f\vert \neq 0 \}= \underset{k=1}{\overset{\infty}{\cup}}\Big\{ \vert f\vert \geq \frac{1}{k} \Big\} , $$
and since the LHS is of uncountable cardinality, at least one the sets in the RHS must also be uncountable, and in particular infinite.

You then have $J\subseteq X$ countable such that $\vert f(j)\vert$ only if $j\in J$. You just have to verify that the supremum of integrals of simple functions is exactly $\sum _{j\in J}|f(j)|$.


问:
Natural deduction for predicate logic
I'm trying to solve this problem:

((∀xFx)→¬(∀xPx))∧(¬(∀xPx)→(∀xFx))→∃x((Fx→¬Px)∧(¬Px→Fx))

I tried double negating the ∃x((Fx→¬Px)∧(¬Px→Fx)), but then I'm getting stuck on what to do next.

How would I solve it after the Implication Introduction?

答:
I tried double negating the ∃x((Fx→¬Px)∧(¬Px→Fx)), but then I'm getting stuck on what to do next.

Basically $\forall x~Fx\leftrightarrow\lnot\forall x~Px$ entails that either (1) $\forall x~Fx$ holds and thus $\exists x~\lnot Px$, or else (2) $\forall x~Fx$ does not hold, and thus $\exists x~\lnot Fx$ and $\forall x~Px$, and we can therefore show either case $\exists x~(Fx\leftrightarrow\lnot Px)$ holds.

The full proof looks to be annoyingly long, but here is the skeleton.

$$\def\fitch#1#2{~~\begin{array}{|l} #1\\\hline #2\end{array}}
\fitch{}{\fitch{(\forall x~Fx)\leftrightarrow(\lnot\forall x~Px)}{\fitch{\lnot\exists x~(Fx\leftrightarrow \lnot Px)}{\fitch{\forall x~Fx}{\lnot\forall x~Px\\~~\vdots\\\exists x~\lnot Px\\~~\vdots\\\exists x~(Fx\leftrightarrow\lnot Px)\\\bot}\\\lnot \forall x~Fx\\~~\vdots\\\forall x~Px\\~~\vdots\\\exists x~\lnot Fx\\~~\vdots\\\exists x~(Fx\leftrightarrow\lnot Px)\\\bot}\\\lnot\lnot \exists x~(Fx\leftrightarrow\lnot Px)\\\exists x~(Fx\leftrightarrow\lnot Px)}\\((\forall x~Fx)\leftrightarrow(\lnot\forall x~Px))\to\exists x~(Fx\leftrightarrow\lnot Px)}$$

Title: Natural deduction for predicate logic


问:
$0$ to the power of $0$ calculus limits
If you take the limit of $x^0$ as $x$ approaches $0$ (from the right), you get that $0^0 = 1$. However, if you take the limit of $0^x$ as $x$ approaches $0$ (from the right), you get $0^0$ = $0$. What is wrong, and doesn't this break calculus?

Also, if you take the limit of $x^x$ as $x$ approaches $0$ (from the right), you get that $0^0 = 1$.

答:
The answer to this lies in the function $f(x,y)=x^y$
simply put, this function is not continuous at (0,0), and in fact, you have just proven this! What you stated only seems to break calculus because we feel like any function involving basic arithmetic operations should be continuous everywhere, therefore taking limits should decide the values these functions hold. However, such is not always the case, and this is a nice example of that.

edit: I should say technically speaking it does not make sense to ask if $f(x,y)=x^y$ is continuous at (0,0) or not, because it is not even defined at (0,0). The right thing to say is that $\lim_{(x,y)\to(0,0)}f(x,y)$ does not exist.

Let me add, another reason you might feel like this breaks calculus is because we are seeing a multivariable function where the limit as $(x,y)\to(0,0)$ does not exist, but there are paths which approach zero where the limit does exist.

for example let $\gamma_1(t)=(0,t)$ then we see that $\lim_{(t)\to(0)}f(\gamma_1(t)))=0$
while if we let $\gamma_2(t)=(t,0)$ then we get $\lim_{(t)\to(0)}f(\gamma_2(t)))=1$
$\gamma_1(t)$ and $\gamma_2(t)$ are both paths which approach (0,0) however we see that both paths approach (0,0) and the limit of $f(x,y)$ does converge on both paths, but it converges to 2 different values. However this is relatively common for multivariable functions for which the limit at a point is not defined. In Fact it is the case that the limit at a point is defined if and only if, the limit is defined for any path approaching that point, and the limit of all paths agree on their values.
Another example of a function which fails at this is the function $g(x,y)=\frac{x}{y}$ it may be more intuitive that in this case the limit as $(x,y)$ approaches (0,0) is not defined, but its not hard to see that there are paths for which the limit is defined, and in fact for every real number, there is a path which converges to that number, and there are also paths which do not converge!

You may think of needing to converge to the same value on every path in multiple dimensions, as being a generalization of the left side limit needing to agree with the right side limit for functions of 1 variable.

Title: $0$ to the power of $0$ calculus limits


答:
I don't see anything wrong here. If you're worried about some purported fagility of calculus, this doesn't break calculus because you are considering the limits as $x\to0^+$ of three different functions; in order, of:

$f:(0,\infty)\to \Bbb R$, $f(x)=x^0$;

$g:(0,\infty)\to\Bbb R$, $g(x)=0^x$;

$h:(0,\infty)\to \Bbb R$, $h(x)=x^x$.

Title: $0$ to the power of $0$ calculus limits

Body:
If you take the limit of $x^0$ as $x$ approaches $0$ (from the right), you get that $0^0 = 1$. However, if you take the limit of $0^x$ as $x$ approaches $0$ (from the right), you get $0^0$ = $0$. What is wrong, and doesn't this break calculus?

Also, if you take the limit of $x^x$ as $x$ approaches $0$ (from the right), you get that $0^0 = 1$.


问:
Recurrence Relation for Bit String Length n with No Consecutive 0s
Consider the following:

Find a recurrence relation and give initial conditions for the number of bit strings of length n that do not have two consecutive 0s.

I am trying to understand the solution to this problem, but I am stuck on this line of the solution:

To obtain a recurrence relation for {an}, note that by the sum rule, the number of bit strings of length n that do not have two consecutive 0s equals the number of such bit strings ending with a 0 plus the number of such bit strings ending with a 1.

I don't understand why this is the case. For example, what if you have a bit string 000, it ends in 0, but has 2 consecutive 0s.

Could someone help me understand this?

答:
This is an old question, but the answer might be helpful to someone. Suppose that $a_n$ gives the number of binary sequences of length $n$ without consecutive 0s. Then we can always add 1 to the end of the sequence to make a sequence of length $n+1$ without consecutive zeros. We can only add a 0 to the end if the sequence ends with a 1, but we can add 10 to the end of any sequence without having consecutive zeros. Hence
$$
 a_{n+1}=a_n+a_{n-1},\quad a_0 = 1, a_1 = 2.
$$


问:
Why is this derivative incorrect?
We have to find the derivative of $$f(x) = \dfrac{\tan(2x)}{\sin(x)}$$

I would like to know why my approach is incorrect:

$$f'(x) = \dfrac{\sin(x) \cdot \dfrac{2}{\cos^2(2x)}  - \tan(2x) \cdot \cos(x)}{\sin^2(x)}$$

$$ =  \dfrac{ 2 \sin(x) - \tan(2x) \cdot \cos(x)}{\cos^2(2x) \cdot \sin^2(x)}$$

$$ = \dfrac {2 \sin(x) - \sin(2x) \cdot \cos(x)}{\cos^3(2x) \cdot \sin^2(x)}$$

p.s. - To avoid confusion ; I wanted to get rid of the $\tan$. I'm sure there is a shorter method than this but I don't want it; I just want to know why this is wrong.

答:
$$f'(x) = \dfrac{\sin(x) \cdot \dfrac{2}{\cos^2(2x)}  - \tan(2x) \cdot \cos(x)}{\sin^2(x)}\tag{1}$$

So far so good...

But your following line is where you made an algebraic error: you forgot to multiply both (the entire numerator (both terms)) and (the denominator) by $\cos^2(2x)$. Doing this gives us:

$$f'(x) = \dfrac{\color{blue}{\bf \cos^2(2x)}\left(\sin(x) \cdot \dfrac{2}{\cos^2(2x)}  - \tan(2x) \cdot \cos(x)\right)}{\color{blue}{\bf \cos^2(2x)}\sin^2(x)}$$

NOW we distribute across the numerator, canceling the denominator of the first term, and multiplying the second term by $\cos^2{2x}$:

$$ =  \dfrac{2\sin(x) - \tan(2x) \cdot \cos(x)\cdot \cos^2(2x)}{\cos^2(2x)\sin^2(x)}\tag{2}$$
$$ = \dfrac{2\sin(x) - \sin(2x) \cdot \cos^2(2x)\cdot \cos(x)}{\cos^3(2x)\sin^2(x)}\tag{3}$$

Title: Why is this derivative incorrect?


问:
$|detA|=1$, $A$ is unitary?
If $A$ is an n by n complex matrix with $|det(A)|=1$, then $A$ is unitary.  ??

I think this statement is false, but I can't seem to find an example to show this. Thanks in advance.

答: $\begin{pmatrix}1&0\\1&1\end{pmatrix}$ is indeed a counterexample. The statement is true only for $n=1$.

Title: $|detA|=1$, $A$ is unitary?


答:
Consider the matrix:
$$
A = \begin{pmatrix}2 & 0 \\
0 &1/2 \end{pmatrix}
$$
Then $\det A = -1$, but notice that:
$$
Ae_1 = 2e_1
$$
So that:
$$
\|Ae_1\| = 2 \|e_1\| = 2 \neq \|e_1\| = 1
$$
So $A$ cannot be unitary.

Title: $|detA|=1$, $A$ is unitary?

Body:
If $A$ is an n by n complex matrix with $|det(A)|=1$, then $A$ is unitary.  ??

I think this statement is false, but I can't seem to find an example to show this. Thanks in advance.


问:
Assigning tasks to minimize cost
I have a set of jobs that must be done on a given day in sequence. $J_1, J_2, J_3$, with deadlines $D_1, D_2, D_3$. There are three workers $W_1, W_2, W_3$ that can execute the tasks each one with varying effects of proficiency $V_1, V_2, V_3$, so a highly proficient worker will do the task in less time, but will also incur a higher cost $C_1, C_2, C_3$. I want to figure out the constraints for a linear program that will execute all tasks within their respective deadline, while minimizing my costs.

I have:
$x_{ij}=
\begin{cases}
1 &\text{if job $i$ executed by worker $j$},\\
0 &\text{otherwise}
\end{cases}$

and one of the constraints I believe should be the fact that I need to choose one, and only, one worker to do the job, so maybe:

$$\sum_{j=1}^3 X_{ij}=1 \quad \text{for $i\in J$}$$

The next constraints that we should consider is obviously the deadline; time to execute previous jobs plus time for current job, since they must be done in sequence (production line), so maybe:

$$\sum_{i=1}^3 \sum_{j=1}^3 T_{ij}X_{ij}\le D_i$$

$$ T_{ij}, i \in J, j \in W $$ is the time that worker $j$ needs to execute job $i$.

Are these constraints correct, or do they make sense in the first place?
If not what should I consider?

答:
First, the deadline constraint as given makes no sense. The summation over $i$ is incorrect.

Given the possibility of a worker doing multiple jobs, one possible fix is as follows. Introduce new variables $L_{ij} \ge 0$, representing the cumulative time worker $j$ spends on any of jobs 1 through $i$ (inclusive) assigned to worker $j$. The values of $L$ are determined by the following constraints (for all workers $j$):
\begin{align*}
L_{1j} & =T_{1j}X_{2j}\\
L_{2j} & =L_{1j}+T_{2j}X_{2j}\\
L_{3j} & =L_{2j}+T_{3j}X_{3j}.
\end{align*}
To enforce the deadlines, add the following constraints for all $j$:
\begin{align*}
L_{1j} & \le D_{1j}\\
L_{2j} & \le D_{2j}+T_{1j}(1-X_{2j})\\
L_{3j} & \le D_{3j}+(T_{1j}+T_{2j})(1-X_{3j}).
\end{align*}
Those constraints ensure that a worker finishes a task by the task's deadline if the worker is doing the task. You already have constraints to ensure that each task is done by a single worker.

Title: Assigning tasks to minimize cost


问:
Categorical Time
I always want to apply category theory to structures that involve "time" or "stepping"/"increment"(discrete "time").

I visualize it as a sequence of categories that are somehow connected(generally the objects are the same and only the morphisms will change, not sure if they are functorially related or not in all cases).

In my cases they are discrete systems in the sense that a morphism does not continuously flow, although, I suppose it should be valid for such systems too(analogous to the calculus of limits).

Is there anything in category theory that deals with this topic? I find that that category theory is more relevant to real systems when time seems to be included but I haven't been able to really apply it with time. In fact, one thing I sort of want to do is have Markovian like structures on categories. A set of categories with probabilistic transitions between them, this too is a sort of category with, I guess, the transitions being functors that are selected with a probability(but in a sequence of steps).

It seems to be category theory generally is thought of as a static structure but this is quite limiting to problems that are actually relatively simple statically but change over time. E.g., imagine a cell phone network where the objects are cell phones and the morphisms are connections. The connections may be off or on(a phone call) and also last for any length of time. Each instant in time there is a category/graph of the network. But over time the graph is dynamically changing. We can even do things like calculus over it.

So, in such ways it looks more like graph theory, BUT, of course, these happen to be categorical structures(identities, composition inclusion, etc)... so the goal is to extract some time-dependent structural variation. E.g., we can think of a typical "basic" category as static in time analogous to a constant function, it's derivative is 0. In this case the categorical structure is dynamic and its "derivative" is not constant but shows how the structure is evolving. Ultimately I want to be able to extract some meta-structure from the evolution of the changing categorical structure(and ultimately derive some type of meta^n-structural deductive chains which would, I hope, ultimately be categorical in nature).

答:
Time is a physical concept and it's a question of how it is to be modelled. It's quite possible that it's an artifact of our modelling that we get time invariance since causal nets, a model in quantum gravity allow, for modelling of time as open - a relatively recent result.

This to me seems a prime suspect in modelling by category theory: the problem being to say something new that hasn't already  been said by causal set theory.

Title: Categorical Time


问:
Fibonacci sequence convergence
I am having trouble expressing the radius $\rho$ with respect to $ z_1 $ and $ z_2 $, and therefore $\alpha$ and $\beta$.

Let    $\sum_{n=0}^{\infty}$ $a_n$$zⁿ$ be an integer series whose coefficients are defined by the following recurrence relations: $a_0 = 0$, $a_1 = 1$ and, for $n ≥ 2$,
$$a_n = αa_{n − 1} + βa_{n − 2}$$ where $α$, $β$ $∈$ $\mathbb{C}$ are different from zero.

Someone can give me hints to do this?

答:
$$a_n = \alpha a_{n − 1} + \beta a_{n − 2}$$
Solve
$$\lambda^2=\alpha\lambda+\beta$$
$$\lambda_1=\frac{\alpha-\sqrt{\alpha ^2+4 \beta }}{2} ;\;\lambda_2=\frac{\alpha+\sqrt{\alpha ^2+4 \beta }}{2} $$
Solution is $$a_n=p\lambda_1^n+q\lambda_2^n$$
as $a_0=1$ we know that $p+q=1$ and as $a_1=2$ we have $p\lambda_1+q\lambda_2=2$

$$p= \frac{\sqrt{\alpha ^2+4 \beta }+\alpha -4}{2 \sqrt{\alpha ^2+4 \beta }},q= \frac{\sqrt{\alpha ^2+4 \beta }-\alpha +4}{2 \sqrt{\alpha ^2+4 \beta }}$$

Finally we have, thanks to Mathematica
$$ \sum_{n=0}^{\infty}a_nz^n=\frac{4 (\alpha  z-2 z-1)}{\left(z \sqrt{\alpha ^2+4 \beta }-\alpha  z+2\right) \left(z \sqrt{\alpha ^2+4 \beta }+\alpha  z-2\right)}$$

Title: Fibonacci sequence convergence


问:
An equivalent expression of Cauchy Criterion?
For a sequence $\{a_n\}$, if
$$
\forall \epsilon>0 \ \exists N>0, \forall k \in \mathbf{N}, \ |a_{N+k}-a_N|<\epsilon \
$$
Then $\{a_n\}$ converges and hence is a Cauchy sequence.

Now how about changing the inequality above to $|a_{N+k}-a_N|< a_{N+k}\cdot \epsilon$, or equivalently $|\frac{a_N}{a_{N+k}} - 1| < \epsilon$? Does the sequence still converge?

答:
Does the sequence still converge?

Yes. Assume the criterion in the question holds and, for every $n\geqslant1$, let $N_n$ such that, for every $j\geqslant i\geqslant N_n$, $|a_i-a_j|\leqslant a_j/2^n$.
Then, for every $j\geqslant N_1$, $\frac23a_{N_1}\leqslant a_j\leqslant2a_{N_1}$, hence $(a_k)$ is bounded.
Furthermore, for every $n\geqslant1$, for every $j\geqslant i\geqslant N_n$, $a_i\leqslant(1+2^{-n}) a_j$ and $(1-2^{-n})a_j\leqslant a_i$ hence
$(1-2^{-n})\limsup a_k\leqslant\liminf a_k$. Thus, $(a_k)$ converges.

Note that the condition
$$
\forall \epsilon>0, \ \exists N>0, \forall k \geqslant0, \ |a_{N+k}-a_N|<a_N\cdot\epsilon,
$$
also implies convergence (the proof is similar).


问:
Fourier transform of function
What is Fourier transform of
$$f(x)=\frac{e^{-|x|}}{\sqrt{|x|}}?$$
I tried to calculate it using
$$F(e^{-|x|})=\sqrt{\frac{\pi}{2}}e^{-|a|}$$
and $$F(\frac{1}{\sqrt{|x|}})=\frac{1}{\sqrt{|a|}}$$
and convolution, but it seems to even more complicated.</p>

答:
$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\on}[1]{\operatorname{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$
\begin{align}
\tilde{\on{f}}\pars{k} & \equiv
\bbox[5px,#ffd]{\int_{-\infty}^{\infty}{%
\expo{-\verts{x}} \over \root{\verts{x}}}\,\expo{\ic k x}\,\dd x} =
2\,\Re\int_{0}^{\infty}{%
\expo{-x} \over \root{x}}\,\expo{\ic k x}\,\dd x
\\[5mm] & =
2\,\Re\int_{0}^{\infty}x^{\color{red}{1/2} - 1}\,\,
\expo{-\pars{1 - \ic k}x}\,\,\,\dd x
\end{align}
Note that
$\ds{\expo{-\pars{1 - \ic k}x}\ = \sum_{0}^{\infty}{\bracks{-\pars{1 - \ic k}x}^{\,n} \over n!} =
\sum_{0}^{\infty}\color{red}{\pars{1 - \ic k}^{n}}
\,\,{\pars{-x}^{\,n} \over n!}}$.

Then,
\begin{align}
\tilde{\on{f}}\pars{k} & =
2\,\Re\bracks{\Gamma\pars{\color{red}{1 \over 2}}
\pars{1 - \ic k}^{-\color{red}{1/2}}}\
\pars{\substack{\ds{Ramanujan's} \\[0.5mm] \ds{Master}\\[0.5mm] \ds{Theorem}}}
\\[5mm] & =
2\root{\pi}\Re\braces{\bracks{\root{1 + k^{2}}\expo{\ic\arctan\pars{-k}}\,\,}^{-1/2}}
\\[5mm] & =
2\root{\pi}\pars{1 + k^{2}}^{-1/4}\,\,
\cos\pars{\arctan\pars{k} \over 2}
\\[5mm] & =
2\root{\pi}\pars{1 + k^{2}}^{-1/4}\,\,
\root{1 + \cos\pars{\arctan\pars{k}} \over 2}
\\[5mm] & =
2\root{\pi}\pars{1 + k^{2}}^{-1/4}\,\,
\root{\sec\pars{\arctan\pars{k}} + 1 \over 2\sec\pars{\arctan\pars{k}}}
\\[5mm] & =
2\root{\pi}\pars{1 + k^{2}}^{-1/4}\,\,
\root{\root{k^{2} + 1} + 1 \over 2\root{k^{2} + 1}}
\\[5mm] & =
\bbx{\root{2\pi}
\root{\root{k^{2} + 1} + 1 \over k^{2} + 1}} \\ &
\end{align}

Title: Fourier transform of function


问:
Distance function differentiable at finite points.
Let $A=[1,2]\cup [3,4]\subset \Bbb{R}$. $x\in \Bbb R$, let $f(x)=\text{inf}\{|x-y|: y\in A\}$. Then the function $f(x)$ is continuous but not differentiable at finitely many point.

Thanks!

答:
Let $A=[1,2]\cup [3,4]\subset \Bbb{R}$. $x\in \Bbb R$, let $f(x)=\text{inf}\{|x-y|: y\in A\}$. Then the function $f(x)$ is continuous but not differentiable at finitely many point.

Since the distance function is uniformly continuous therefore $f(x)$ is continuous.

It remains to show that $f(x)$ is not differentiable at finitely many points.

distance from any point(less than 1) to the set $A$ and then distance from any point to the set
$A$(greater than 3). We have two slopes from the left most and the right most. Then slope continues from 2 to 3. Then we have sharp edge between 2 and 3 and also sharp edge at 1,2,3,4 and between 2 and 3.  For a function differentiable at some point the slope has to be continuous.


答:
You second proposition is actually only defined if the sequence is always non-zero after some $n$. Otherwise, if it takes value $0$ infinitely often, then you cannot even write the criterion you suggest.

As André Nicolas pointed out, for the first one, take $0 < \alpha < 1$, and set $a_n\stackrel{\rm{}def}{=} a^n$. It does converge, but your criterion would imply that
$$
\forall k\in\mathbb{N},\quad |a^k-1|\leq a^k\varepsilon
$$
the LHS goes to 1, the RHS to $0$. So your criterion would not be even allow you to conclude for rather elementary sequences...

In both cases, regardless of whatever it still implies convergence, the criterion would not be a very good tool to use.

Title: An equivalent expression of Cauchy Criterion?

Body:
For a sequence $\{a_n\}$, if
$$
\forall \epsilon>0 \ \exists N>0, \forall k \in \mathbf{N}, \ |a_{N+k}-a_N|<\epsilon \
$$
Then $\{a_n\}$ converges and hence is a Cauchy sequence.

Now how about changing the inequality above to $|a_{N+k}-a_N|< a_{N+k}\cdot \epsilon$, or equivalently $|\frac{a_N}{a_{N+k}} - 1| < \epsilon$? Does the sequence still converge?


问:
Solving a second order PDE in canonical form
I have to solve the PDE: $$yu_{xx} + (x + y)u_{xy} + xu_{yy} = 0$$ I've found it's hyperbolic whenever $y\not=x$ and its canonical form is $u_{\phi\psi}=-\frac{1}{\psi}u_\phi$

I'm at a bit of a loss as to what to do now.. Can I set $z=u_\phi$ and then treat it as an ODE?

Body:
Yes that's what you have to do:
$$u_{\phi\psi}=-\frac{1}{\psi}u_\phi$$
$$z_{\psi}=-\frac{1}{\psi}z$$
$$\psi z_{\psi}+z=0$$
$$(\psi z)'=0$$
$$\psi z=C_1(\phi)$$
Where $z=u_{\phi}$.
$$\psi u_{\phi}=C_1(\phi)$$
$$u({\psi},\phi)=\dfrac {g(\phi)}{\psi}+f(\psi)$$


问:
Asymptotics of number of points of elliptic curves over finite fields
For an elliptic curve $E$ over a finite field $\mathbb F_q$, let $a_q(E) = q+1 - |E(\mathbb F_q)|$. Hasse--Weil bound tells us that $|a_q(E)| \leq 2 \sqrt{q}$.

I am interesting in knowing how large/small can $2 \sqrt{q} - a_q$ be. For instance, is there a sequence of primes $(p_k)$ and elliptic curves $E_k$ over $\mathbb F_{p_k}$ such that
$$b(E_k) := (2 \sqrt{p_k} - a_{p_k}(E_k)) / \log(p_k) \to 0$$ ?

I know that 1) Sato--Tate distribution describes the distribution of $a_p(E) / (2 \sqrt{p})$, but here we are looking at the difference between $a_p$ and $2 \sqrt{p}$, not the quotient, and 2) supersingular curves show that $b(E_k)$ can go to infinity.

答:
Given a fixed prime power $q = p^n$ (with $p$ prime), Waterhouse (1969) gives a complete description of which numbers can occur as $\#E(\mathbb{F}_q)$ for some elliptic curve $E$ over the finite field $\mathbb{F}_q$. In particular, the extremal cases $a_q = \pm 2 \sqrt{q}$ do occur (for some $E$) whenever $q$ is a perfect square (i.e., whenever $n$ is even).

Rück (1987) goes further and describes all possible group structures for $E(\mathbb{F}_q)$. These papers were brought to my attention by this answer of Joe Silverman to a related question on MathOverflow.

References:

MR0265369, Waterhouse, William C., Abelian varieties over finite fields. Ann. Sci. École Norm. Sup. (4) 2 1969 521–560.

MR0890272, Rück, Hans-Georg, A note on elliptic curves over finite fields. Math. Comp. 49 (1987), no. 179, 301–304.


问:
Determine if integer can be factored as $ab(a+b)$
For $N,a,b \in \mathbb{Z}$ and distinct $a,b>1$, how can I determine if it is possible to factor $N$ as any $a \times b \times (a+b)$? (I don't necessarily need all $a,b$ if that helps...)

My first thought was to factor $N$, then enumerate the factors into three buckets, $a$, $b$, and \$leftover, then check if \$leftover equals $a+b$. But this grows quite badly, for n total factors ~ $\mathcal{O}(n!)$ (OEIS A200978), so this approach seems infeasible.

Body:
First note that $ab(a+b)=n$ implies

$$a(-a-b)(a+(-a-b))=n$$

and so $(a,-a-b)$ is also a solution, plus obviously $(b,a)$ by symmetry. If you compose them you get a group of 6 possible solutions but sometimes they overlap. That group happens to be isomorphic to $S_3$. To transform into an elliptic curve let $q=\frac a b$ then

$$b^3q(q+1)=n$$

$$q^2+q=nb^{-3}$$

$$(2q+1)^2=1+4nb^{-3}$$

$$(4n(2q+1))^2=16n^2+\left(\frac{4n}b\right)^3$$

Let $y=4n(2q+1)$ and $x=\frac{4n}b$ and we have an elliptic curve

$$y^2=x^3+16n^2$$

And the reverse transform is $a=\frac{y-4n}{2x}$, $b=\frac{4n}x$. This curve has the trivial points $(x,y)=(0,\pm 4n)$. Those points sum to the identity so call them $\pm P$, we have that $P+P=-P$ so they're elements of order 3. I did a bit of computation with sage:

for i in range(1,100):
    print(i, EllipticCurve([0,0,0,0,16*i^2]).torsion_points(), EllipticCurve([0,0,0,0,16*i^2]).gens())
1 [(0 : -4 : 1), (0 : 1 : 0), (0 : 4 : 1)] []
2 [(-4 : 0 : 1), (0 : -8 : 1), (0 : 1 : 0), (0 : 8 : 1), (8 : -24 : 1), (8 : 24 : 1)] []
3 [(0 : -12 : 1), (0 : 1 : 0), (0 : 12 : 1)] []
4 [(0 : -16 : 1), (0 : 1 : 0), (0 : 16 : 1)] []
5 [(0 : -20 : 1), (0 : 1 : 0), (0 : 20 : 1)] []
6 [(0 : -24 : 1), (0 : 1 : 0), (0 : 24 : 1)] [(-8 : 8 : 1)]
7 [(0 : -28 : 1), (0 : 1 : 0), (0 : 28 : 1)] [(8 : 36 : 1)]
8 [(0 : -32 : 1), (0 : 1 : 0), (0 : 32 : 1)] []
9 [(0 : -36 : 1), (0 : 1 : 0), (0 : 36 : 1)] [(-8 : 28 : 1)]
10 [(0 : -40 : 1), (0 : 1 : 0), (0 : 40 : 1)] []
11 [(0 : -44 : 1), (0 : 1 : 0), (0 : 44 : 1)] []
12 [(0 : -48 : 1), (0 : 1 : 0), (0 : 48 : 1)] [(-12 : 24 : 1)]
13 [(0 : -52 : 1), (0 : 1 : 0), (0 : 52 : 1)] [(273 : 4511 : 1)]
14 [(0 : -56 : 1), (0 : 1 : 0), (0 : 56 : 1)] []
15 [(0 : -60 : 1), (0 : 1 : 0), (0 : 60 : 1)] [(24 : 132 : 1)]
16 [(-16 : 0 : 1), (0 : -64 : 1), (0 : 1 : 0), (0 : 64 : 1), (32 : -192 : 1), (32 : 192 : 1)] []
17 [(0 : -68 : 1), (0 : 1 : 0), (0 : 68 : 1)] [(8568 : 793084 : 1)]
18 [(0 : -72 : 1), (0 : 1 : 0), (0 : 72 : 1)] []
19 [(0 : -76 : 1), (0 : 1 : 0), (0 : 76 : 1)] [(24 : 140 : 1), (1824 : 77900 : 1)]
20 [(0 : -80 : 1), (0 : 1 : 0), (0 : 80 : 1)] [(-16 : 48 : 1)]
21 [(0 : -84 : 1), (0 : 1 : 0), (0 : 84 : 1)] []
22 [(0 : -88 : 1), (0 : 1 : 0), (0 : 88 : 1)] [(48 : 344 : 1)]
23 [(0 : -92 : 1), (0 : 1 : 0), (0 : 92 : 1)] []
24 [(0 : -96 : 1), (0 : 1 : 0), (0 : 96 : 1)] []
25 [(0 : -100 : 1), (0 : 1 : 0), (0 : 100 : 1)] []
26 [(0 : -104 : 1), (0 : 1 : 0), (0 : 104 : 1)] [(12 : 112 : 1)]
27 [(0 : -108 : 1), (0 : 1 : 0), (0 : 108 : 1)] []
28 [(0 : -112 : 1), (0 : 1 : 0), (0 : 112 : 1)] [(-12 : 104 : 1)]
29 [(0 : -116 : 1), (0 : 1 : 0), (0 : 116 : 1)] []
30 [(0 : -120 : 1), (0 : 1 : 0), (0 : 120 : 1)] [(-24 : 24 : 1), (-20 : 80 : 1)]
31 [(0 : -124 : 1), (0 : 1 : 0), (0 : 124 : 1)] [(8905/441 : 1422989/9261 : 1)]
32 [(0 : -128 : 1), (0 : 1 : 0), (0 : 128 : 1)] []
33 [(0 : -132 : 1), (0 : 1 : 0), (0 : 132 : 1)] [(-24 : 60 : 1)]
34 [(0 : -136 : 1), (0 : 1 : 0), (0 : 136 : 1)] [(-16 : 120 : 1)]
35 [(0 : -140 : 1), (0 : 1 : 0), (0 : 140 : 1)] [(-24 : 76 : 1)]
36 [(0 : -144 : 1), (0 : 1 : 0), (0 : 144 : 1)] []
37 [(0 : -148 : 1), (0 : 1 : 0), (0 : 148 : 1)] [(48 : 364 : 1), (4440 : 295852 : 1)]
38 [(0 : -152 : 1), (0 : 1 : 0), (0 : 152 : 1)] []
39 [(0 : -156 : 1), (0 : 1 : 0), (0 : 156 : 1)] []
40 [(0 : -160 : 1), (0 : 1 : 0), (0 : 160 : 1)] []
41 [(0 : -164 : 1), (0 : 1 : 0), (0 : 164 : 1)] []
42 [(0 : -168 : 1), (0 : 1 : 0), (0 : 168 : 1)] [(-24 : 120 : 1)]
43 [(0 : -172 : 1), (0 : 1 : 0), (0 : 172 : 1)] [(2408 : 118164 : 1)]
44 [(0 : -176 : 1), (0 : 1 : 0), (0 : 176 : 1)] []
45 [(0 : -180 : 1), (0 : 1 : 0), (0 : 180 : 1)] []
46 [(0 : -184 : 1), (0 : 1 : 0), (0 : 184 : 1)] []
47 [(0 : -188 : 1), (0 : 1 : 0), (0 : 188 : 1)] []
48 [(0 : -192 : 1), (0 : 1 : 0), (0 : 192 : 1)] [(-32 : 64 : 1)]
49 [(0 : -196 : 1), (0 : 1 : 0), (0 : 196 : 1)] [(1617 : 65023 : 1)]
50 [(0 : -200 : 1), (0 : 1 : 0), (0 : 200 : 1)] [(24 : 232 : 1)]
51 [(0 : -204 : 1), (0 : 1 : 0), (0 : 204 : 1)] [(144 : 1740 : 1)]
52 [(0 : -208 : 1), (0 : 1 : 0), (0 : 208 : 1)] []
53 [(0 : -212 : 1), (0 : 1 : 0), (0 : 212 : 1)] [(13620672/47089 : 50315372428/10218313 : 1)]
54 [(-36 : 0 : 1), (0 : -216 : 1), (0 : 1 : 0), (0 : 216 : 1), (72 : -648 : 1), (72 : 648 : 1)] []
55 [(0 : -220 : 1), (0 : 1 : 0), (0 : 220 : 1)] []
56 [(0 : -224 : 1), (0 : 1 : 0), (0 : 224 : 1)] [(32 : 288 : 1)]
57 [(0 : -228 : 1), (0 : 1 : 0), (0 : 228 : 1)] []
58 [(0 : -232 : 1), (0 : 1 : 0), (0 : 232 : 1)] [(-24 : 200 : 1)]
59 [(0 : -236 : 1), (0 : 1 : 0), (0 : 236 : 1)] []
60 [(0 : -240 : 1), (0 : 1 : 0), (0 : 240 : 1)] []
61 [(0 : -244 : 1), (0 : 1 : 0), (0 : 244 : 1)] [(80 : 756 : 1)]
62 [(0 : -248 : 1), (0 : 1 : 0), (0 : 248 : 1)] [(-308/9 : 3952/27 : 1)]
63 [(0 : -252 : 1), (0 : 1 : 0), (0 : 252 : 1)] [(16 : 260 : 1)]
64 [(0 : -256 : 1), (0 : 1 : 0), (0 : 256 : 1)] []
65 [(0 : -260 : 1), (0 : 1 : 0), (0 : 260 : 1)] [(-40 : 60 : 1), (-39 : 91 : 1)]
66 [(0 : -264 : 1), (0 : 1 : 0), (0 : 264 : 1)] []
67 [(0 : -268 : 1), (0 : 1 : 0), (0 : 268 : 1)] [(-25865696/1750329 : 606501324260/2315685267 : 1)]
68 [(0 : -272 : 1), (0 : 1 : 0), (0 : 272 : 1)] [(240 : 3728 : 1)]
69 [(0 : -276 : 1), (0 : 1 : 0), (0 : 276 : 1)] [(-23 : 253 : 1)]
70 [(0 : -280 : 1), (0 : 1 : 0), (0 : 280 : 1)] [(-40 : 120 : 1)]
71 [(0 : -284 : 1), (0 : 1 : 0), (0 : 284 : 1)] [(99288/1849 : 38582996/79507 : 1)]
72 [(0 : -288 : 1), (0 : 1 : 0), (0 : 288 : 1)] [(-32 : 224 : 1)]
73 [(0 : -292 : 1), (0 : 1 : 0), (0 : 292 : 1)] []
74 [(0 : -296 : 1), (0 : 1 : 0), (0 : 296 : 1)] []
75 [(0 : -300 : 1), (0 : 1 : 0), (0 : 300 : 1)] [(-24 : 276 : 1)]
76 [(0 : -304 : 1), (0 : 1 : 0), (0 : 304 : 1)] []
77 [(0 : -308 : 1), (0 : 1 : 0), (0 : 308 : 1)] []
78 [(0 : -312 : 1), (0 : 1 : 0), (0 : 312 : 1)] [(-39 : 195 : 1)]
79 [(0 : -316 : 1), (0 : 1 : 0), (0 : 316 : 1)] [(3081/4 : 171035/8 : 1)]
80 [(0 : -320 : 1), (0 : 1 : 0), (0 : 320 : 1)] []
81 [(0 : -324 : 1), (0 : 1 : 0), (0 : 324 : 1)] []
82 [(0 : -328 : 1), (0 : 1 : 0), (0 : 328 : 1)] []
83 [(0 : -332 : 1), (0 : 1 : 0), (0 : 332 : 1)] []
84 [(0 : -336 : 1), (0 : 1 : 0), (0 : 336 : 1)] [(-48 : 48 : 1)]
85 [(0 : -340 : 1), (0 : 1 : 0), (0 : 340 : 1)] [(-15 : 335 : 1)]
86 [(0 : -344 : 1), (0 : 1 : 0), (0 : 344 : 1)] [(-48 : 88 : 1), (504 : 11320 : 1)]
87 [(0 : -348 : 1), (0 : 1 : 0), (0 : 348 : 1)] [(840 : 24348 : 1)]
88 [(0 : -352 : 1), (0 : 1 : 0), (0 : 352 : 1)] []
89 [(0 : -356 : 1), (0 : 1 : 0), (0 : 356 : 1)] [(-7632/169 : 408884/2197 : 1)]
90 [(0 : -360 : 1), (0 : 1 : 0), (0 : 360 : 1)] [(-36 : 288 : 1)]
91 [(0 : -364 : 1), (0 : 1 : 0), (0 : 364 : 1)] [(-455/9 : -1547/27 : 1), (273/4 : -5369/8 : 1)]
92 [(0 : -368 : 1), (0 : 1 : 0), (0 : 368 : 1)] [(48 : 496 : 1)]
93 [(0 : -372 : 1), (0 : 1 : 0), (0 : 372 : 1)] []
94 [(0 : -376 : 1), (0 : 1 : 0), (0 : 376 : 1)] [(25200 : 4000376 : 1)]
95 [(0 : -380 : 1), (0 : 1 : 0), (0 : 380 : 1)] []
96 [(0 : -384 : 1), (0 : 1 : 0), (0 : 384 : 1)] [(-48 : 192 : 1)]
97 [(0 : -388 : 1), (0 : 1 : 0), (0 : 388 : 1)] [(280/9 : 11476/27 : 1)]
98 [(0 : -392 : 1), (0 : 1 : 0), (0 : 392 : 1)] [(60 : 608 : 1)]
99 [(0 : -396 : 1), (0 : 1 : 0), (0 : 396 : 1)] []
100 [(0 : -400 : 1), (0 : 1 : 0), (0 : 400 : 1)] []

A conjecture that the torsion group is always isomorphic to $C_3$ when $n$ is not twice a cube sounds reasonable. Excepting that case, when the curve has rank greater than 0 we get infinitely many rational solutions but not necessarily integral ones. The sequence of $n$ so that the rank is not 0 matches the sequence of integers which are the sum of two rational cubes but not cubes or twice cubes themselves. From here I don't know how to proceed.


问:
Can Dirichlet characters mod q only agree on the same congruence class?
In my lecture notes for an analytic number theory module, the lecturer (I think) implicitly uses that, for $(a,q)=1$, if $\chi(a)=\chi(n)$ for all Dirichlet characters $\chi\mod q$, then $n\equiv a \mod q$. Looking at the table of the first few characters on Wikipedia, I can believe this is true. So, is this true? And if so, how would I prove it?

答:
The Dirichlet characters $\bmod q$ correspond to the characters $\Bbb{Z/qZ^\times\to C^\times}$. Given some $b\ne 1\in \Bbb{Z/qZ^\times}$ (here $b= an^{-1}$) start with $H_1=\langle b\rangle$ and a non-trivial character $\chi_1$ of $H_1$, then for $k=1,2,\ldots$, take $x_{k+1}\not \in H_k$, let $H_{k+1}=\langle H_k,x_{k+1}\rangle$, let $e_{k+1}$ be the least natural number such that $x_{k+1}^{e_{k+1}}\in H_k$ and set $\chi_{k+1}(x_{k+1}) = \chi_k(x_{k+1})^{1/e_{k+1}}$.

At some point there is no such $x_{k+1}$ and $\chi_k$ is a character of $\Bbb{Z/qZ^\times}$ such that $\chi_k(b)\ne 1$. Moreover if $\langle b\rangle$ was a maximal cyclic subgroup and $\chi_1(b)$ had the same order as $b$ then $G=\langle b\rangle\times \ker(\chi_k)$.


问:
Number of Solutions for Congruency Equations
I'm leaning congruency equations, so for example:
$$
    ax \equiv b \pmod m
$$
I have that the number of solutions will be equal to $d$, where
$$
    d = \gcd(a, m).
$$
And the solutions ae:
$$
    x, x+m/d, x+2m/d, x+3m/d, \ldots , x+(d-1)m/d
$$
Now, having understood how I solve the equation, I am still not entirely sure as to why the number of solutions is given by $d$...

Anybody can calrify please?

Cheers! :)

答:
If you scroll down on this pdf you will find a complete proof of this
http://www.math.niu.edu/~richard/Math420/lin_cong.pdf

I couldn't be bothered to type it up. Sorry.


问:
Problem regarding the definition of field of rational-functions over $k$.
In the construction of $\operatorname{Frac}(R)$, where $R$ is a domain, we define a partition on $R \times R^\times$ where $R^\times:= R \setminus \{0\}$. which in turn becomes a field containing $R$.

Taking $R:=\mathbb{Q}[x]$, can we tell that $\frac{x^2+1}{x-1} \in \mathbb{Q}(x)$? As $x-1$ is not the zero-polynomial it is a member of $\mathbb{Q}[x]^\times$, hence $\frac{x^2+1}{x-1}$ should be a member of $\mathbb{Q}(x)$. But this is undefined when 1 is plugged in $x$.

Where am I going wrong?

答:
The simple answer is that elements of $\mathbb{Q}(x)$ are formal rational functions. strictly speaking, the values they take on at certain points are irrelevant to them. Their evaluation maps need not be defined for all elements in the underlying field.
Another example is that $\frac{1}{x}$ which is the multiplicative inverse of $x$ is not defined as a function at $x=0$. That's fine because the way we are looking at it, $\frac{1}{x}$ is not actually a function, it's really just the formal inverse of $x$.

There is a similar intuition here to how $x^2+x+1\in\mathbb{F}_2[x]$ is not the same thing as $1\in\mathbb{F}_2[x]$ even though the evaluation maps are the same.

$x$ is just something that is transcendental over $\mathbb{Q}$ we think of the elements of $\mathbb{Q}(x)$ as being rational functions, but really we shouldn't be considering any of their properties as functions in the context of algebra. It's helpful to realise that $\mathbb{Q}(x)$ is isomorphic to $\mathbb{Q}(\pi)$


问:
Is it possible to find the area of a triangle from the length of one side and the measure of the opposite angle?
Sorry for maybe stupid question, because I'm pretty sure the context is incomplete, but anyway.

Given $$ \triangle ABC; AC = 4 cm; \angle ABC = 45°; S \triangle ABC-? $$

That's all. Is there a way to solve this?

答:
Hint:

That's right, there in not enough data to find the area of $\triangle ABC$,
however, we can state that it can't be greater
than
\begin{align}
S_{ABC}
&\le
\tfrac14\,|AC|^2\,\cot\tfrac12\angle ABC
.
\end{align}


问:
Need help to do question E) only
[enter image description here][1]

the question picture here [1]: https://i.stack.imgur.com/DbwtU.png

答:
So we already know by a) and b) that $V=\ker P\oplus{\rm ran}\,P$ where $\ker P$ is the eigenspace for eigenvalue $0$ and ${\rm ran}\,P$, the range of $P$, is the eigenspace for eigenvalue $1$.

Additionally, d) implies that with the assumption $\forall v:\|P(v)\|\le\|v\|$ of e), we also have $\ker P\perp{\rm ran}\,P$.

Now, if $v=v_1+v_2,\ w=w_1+w_2$ with $v_1,w_1\in{\rm ran}\,P,\ v_2,w_2\in\ker P$ (specifically $v_1=P(v),\,w_1=P(w)$), then
$$\langle P(v),w\rangle=\langle v_1,w_1\rangle=\langle v,P(w)\rangle$$

Title: Need help to do question E) only


问:
What does "$\max_{x>0}$" mean in $\max_{x > 0} \min_{1 \leq i \leq n} \frac 1{x_i} \sum_{j=1}^n a_{ij}x_j$?

Corrolary 8.1.31. Let $A = [a_{ij}] \in M_n$ be nonnegative. If $A$ has a positive eigenvector, then
$$
\rho(A) = \max_{x > 0} \min_{1 \leq i \leq n} \frac 1{x_i} \sum_{j=1}^n a_{ij}x_j
= \min_{x > 0} \max_{1 \leq i \leq n} \frac 1{x_i} \sum_{j=1}^n a_{ij} x_j.
$$

(link to original image)

Can someone please help me read this notationally?

What does the "$\max_{x>0}$" mean?

答:
In this context, $x > 0$ means that the vector $x \in \Bbb C^n$ is such that each of its entries is greater than $0$. That is, $x = (x_1,\dots,x_n)$ with $x_j > 0$ for $j = 1,\dots,n$.

With that established, we can rewrite
$$
\max_{x > 0}\min_{1 \leq i \leq n} \frac 1{x_i} \sum_{j=1}^n a_{ij}x_j =
\max \left\{ \min\left\{\frac 1{x_i} \sum_{j=1}^n a_{ij}x_j : 1 \leq i \leq n \right\}:x = (x_1,\dots,x_n) > 0\right\},
$$
where $\max(S)$ denotes the maximum element of a set $S$.


答:
Unpacking this statement, this says that $\rho(A)$ is equal to the largest value among all $x > 0$ of $f(x)$, where $f(x)$ is equal to the smallest value among all $1 \leq i \leq n$ of $g(x,i)$, where $g(x,i) = \frac{1}{x_i}\sum\limits_{j=1}^na_{ij}x_j$.

Specifically, $\max\limits_{x > 0}$ means "of all of the possible values that we could get out by putting different $x$ in there, the one that gives the biggest number".

Title: What does "$\max_{x>0}$" mean in $\max_{x > 0} \min_{1 \leq i \leq n} \frac 1{x_i} \sum_{j=1}^n a_{ij}x_j$?

Body:
Corrolary 8.1.31. Let $A = [a_{ij}] \in M_n$ be nonnegative. If $A$ has a positive eigenvector, then
$$
\rho(A) = \max_{x > 0} \min_{1 \leq i \leq n} \frac 1{x_i} \sum_{j=1}^n a_{ij}x_j
= \min_{x > 0} \max_{1 \leq i \leq n} \frac 1{x_i} \sum_{j=1}^n a_{ij} x_j.
$$

(link to original image)

Can someone please help me read this notationally?

What does the "$\max_{x>0}$" mean?


问:
Let $(A,B)$ be a bipartition with $|A|=|B|=n$, show that if $\Delta(G)$ is at most $\epsilon^2n$ then the pair $(A,B)$ is $\epsilon$-regular
Suppose $G$ is a bipartite graph with bipartition $(A,B)$ with $|A|=|B|=n$, show that if the maximum degree of $G$ is at most $\epsilon^2n$ then the pair $(A,B)$ is $\epsilon$-regular.

So here’s my thought process:

Let $A’\subseteq A$ and $B’\subseteq B$ with $|A’|\geq\epsilon |A|$ and $|B’|\geq\epsilon |B|$. Now I need to show that $|d(A,B)-d(A’,B’)|<\epsilon$.

I have $d(A,B)-d(A’,B’)=\frac{||G||}{n^2}-\frac{||A’,B’||}{|A’||B’|}\leq\frac{||G||}{n^2}-\frac{||A’,B’||}{\epsilon^2n^2}$. I don’t know if I should say $||G||\leq\epsilon^2n^2$ based on the degree condition, and therefore I have $d(A,B)-d(A’,B’)\leq\epsilon^2-\frac{||A’,B’||}{\epsilon^2n^2}$. But even then, I’m not sure how to proceed from there.

Any help would be appreciated!

答:
First, you aren't being very careful: $d(A', B') = \frac{\|A', B'\|}{|A'| |B'|}$, which is not necessarily the same as $\frac{\|A',B'\|}{\epsilon^2 n^2}$. It's true that $\frac{\|A',B'\|}{\epsilon^2 n^2}$ is an upper bound, but it's not one we want to use at this stage, because $\|A',B'\|$ can be much larger when $A'$ and $B'$ are closer to $n$ than $\epsilon n$ in size.

Second, in order to bound $\frac{\|A', B'\|}{|A'| |B'|}$: every vertex in $A'$ has at most $\epsilon^2 n$ neighbors; in particular, at most $\epsilon^2 n$ neighbors in $B'$. Therefore $\|A', B'\| \le \epsilon^2 n |A'|$.

You should be able to use this to show that $d(A', B') \le \epsilon$, and conclude $|d(A,B) - d(A',B')| \le \epsilon$ from there.