问:
Why doesn't Scipy's wasserstein_distance use linear programming?

Question

Kantorovich's formulation of the optimal transport problem using the Wasserstein distance is

$$\begin{align}\begin{aligned}W_p(a,b)=(\min_\gamma \sum_{i,j}\gamma_{i,j}\|x_i-y_j\|_p)^\frac{1}{p}\\s.t. \gamma 1 = a; \gamma^T 1= b; \gamma\geq 0\end{aligned}\end{align}$$

It is often taught that this is solved using linear programming:

$$\begin{align}\begin{aligned}OT(a,b)=\min_\gamma \quad \sum_{i,j}\gamma_{i,j}M_{i,j}\\s.t. \gamma 1 = a; \gamma^T 1= b; \gamma\geq 0\end{aligned}\end{align}$$

How then is the function scipy.stats.wasserstein_distance able to solve Wasserstein/OT without linear programming? What approach/method is the function using?

My guess

I am aware that wasserstein_distance is for 1D distributions only, and there so happens to be a closed-form analytical solution in the 1D case which is

$$\mathcal{W}_{p}(\mu, \nu) =\left(\int_{0}^{1}\left|F_{\mu}^{-1}(z)-F_{\nu}^{-1}(z)\right|^{p} \mathrm{d} z\right)^{\frac{1}{p}}$$

The formula above contains inverse probability functions $F^{-1}$. The code, shown next, however, does not contain inverse probability functions from what I can see.

Code

I know this sounds like a stackoverflow question, but it's not (and I need to write the math formulas): I'm trying to figure out what formula/approach is being used by the code since the code does not resemble anything above: It doesn't use linear programming, otherwise we would see scipy.optimize.linprog somewhere, and it doesn't use inverse probability, otherwise we would see .ppf somewhere:

```<code>def wasserstein_distance(u_values, v_values, u_weights=None, v_weights=None):
    r"""
    Compute the first Wasserstein distance between two 1D distributions.
    This distance is also known as the earth mover's distance, since it can be
    seen as the minimum amount of "work" required to transform :math:`u` into
    :math:`v`, where "work" is measured as the amount of distribution weight
    that must be moved, multiplied by the distance it has to be moved.
    .. versionadded:: 1.0.0
    Parameters
    ----------
    u_values, v_values : array_like
        Values observed in the (empirical) distribution.
    u_weights, v_weights : array_like, optional
        Weight for each value. If unspecified, each value is assigned the same
        weight.
        `u_weights` (resp. `v_weights`) must have the same length as
        `u_values` (resp. `v_values`). If the weight sum differs from 1, it
        must still be positive and finite so that the weights can be normalized
        to sum to 1.
    Returns
    -------
    distance : float
        The computed distance between the distributions.
    Notes
    -----
    The first Wasserstein distance between the distributions :math:`u` and
    :math:`v` is:
    .. math::
        l_1 (u, v) = \inf_{\pi \in \Gamma (u, v)} \int_{\mathbb{R} \times
        \mathbb{R}} |x-y| \mathrm{d} \pi (x, y)
    where :math:`\Gamma (u, v)` is the set of (probability) distributions on
    :math:`\mathbb{R} \times \mathbb{R}` whose marginals are :math:`u` and
    :math:`v` on the first and second factors respectively.
    If :math:`U` and :math:`V` are the respective CDFs of :math:`u` and
    :math:`v`, this distance also equals to:
    .. math::
        l_1(u, v) = \int_{-\infty}^{+\infty} |U-V|
    See [2]_ for a proof of the equivalence of both definitions.
    The input distributions can be empirical, therefore coming from samples
    whose values are effectively inputs of the function, or they can be seen as
    generalized functions, in which case they are weighted sums of Dirac delta
    functions located at the specified values.
    References
    ----------
    .. [1] "Wasserstein metric", https://en.wikipedia.org/wiki/Wasserstein_metric
    .. [2] Ramdas, Garcia, Cuturi "On Wasserstein Two Sample Testing and Related
           Families of Nonparametric Tests" (2015). :arXiv:`1509.02237`.
    Examples
    --------
    >>> from scipy.stats import wasserstein_distance
    >>> wasserstein_distance([0, 1, 3], [5, 6, 8])
    5.0
    >>> wasserstein_distance([0, 1], [0, 1], [3, 1], [2, 2])
    0.25
    >>> wasserstein_distance([3.4, 3.9, 7.5, 7.8], [4.5, 1.4],
    ...                      [1.4, 0.9, 3.1, 7.2], [3.2, 3.5])
    4.0781331438047861
    """
    return _cdf_distance(1, u_values, v_values, u_weights, v_weights)

def _cdf_distance(p, u_values, v_values, u_weights=None, v_weights=None):
    r"""
    Compute, between two one-dimensional distributions :math:`u` and
    :math:`v`, whose respective CDFs are :math:`U` and :math:`V`, the
    statistical distance that is defined as:
    .. math::
        l_p(u, v) = \left( \int_{-\infty}^{+\infty} |U-V|^p \right)^{1/p}
    p is a positive parameter; p = 1 gives the Wasserstein distance, p = 2
    gives the energy distance.
    Parameters
    ----------
    u_values, v_values : array_like
        Values observed in the (empirical) distribution.
    u_weights, v_weights : array_like, optional
        Weight for each value. If unspecified, each value is assigned the same
        weight.
        `u_weights` (resp. `v_weights`) must have the same length as
        `u_values` (resp. `v_values`). If the weight sum differs from 1, it
        must still be positive and finite so that the weights can be normalized
        to sum to 1.
    Returns
    -------
    distance : float
        The computed distance between the distributions.
    Notes
    -----
    The input distributions can be empirical, therefore coming from samples
    whose values are effectively inputs of the function, or they can be seen as
    generalized functions, in which case they are weighted sums of Dirac delta
    functions located at the specified values.
    References
    ----------
    .. [1] Bellemare, Danihelka, Dabney, Mohamed, Lakshminarayanan, Hoyer,
           Munos "The Cramer Distance as a Solution to Biased Wasserstein
           Gradients" (2017). :arXiv:`1705.10743`.
    """
    u_values, u_weights = _validate_distribution(u_values, u_weights)
    v_values, v_weights = _validate_distribution(v_values, v_weights)

    u_sorter = np.argsort(u_values)
    v_sorter = np.argsort(v_values)

    all_values = np.concatenate((u_values, v_values))
    all_values.sort(kind='mergesort')

    # Compute the differences between pairs of successive values of u and v.
    deltas = np.diff(all_values)

    # Get the respective positions of the values of u and v among the values of
    # both distributions.
    u_cdf_indices = u_values[u_sorter].searchsorted(all_values[:-1], 'right')
    v_cdf_indices = v_values[v_sorter].searchsorted(all_values[:-1], 'right')

    # Calculate the CDFs of u and v using their weights, if specified.
    if u_weights is None:
        u_cdf = u_cdf_indices / u_values.size
    else:
        u_sorted_cumweights = np.concatenate(([0],
                                              np.cumsum(u_weights[u_sorter])))
        u_cdf = u_sorted_cumweights[u_cdf_indices] / u_sorted_cumweights[-1]

    if v_weights is None:
        v_cdf = v_cdf_indices / v_values.size
    else:
        v_sorted_cumweights = np.concatenate(([0],
                                              np.cumsum(v_weights[v_sorter])))
        v_cdf = v_sorted_cumweights[v_cdf_indices] / v_sorted_cumweights[-1]

    # Compute the value of the integral based on the CDFs.
    # If p = 1 or p = 2, we avoid using np.power, which introduces an overhead
    # of about 15%.
    if p == 1:
        return np.sum(np.multiply(np.abs(u_cdf - v_cdf), deltas))
    if p == 2:
        return np.sqrt(np.sum(np.multiply(np.square(u_cdf - v_cdf), deltas)))
    return np.power(np.sum(np.multiply(np.power(np.abs(u_cdf - v_cdf), p),
                                       deltas)), 1/p)
</code>```

答:
A more complete explanation for the algorithm used is in Remark 2.28 of the book Computational Optimal Transport. But a brief explanation of how the algorithm works is the following:

We are dealing with a 1-D case with two Discrete distributions where we want to transport $\alpha$ to $\beta$. Now, you sort the distribution and from left to right, you move each mass of $\beta$ to the closest mass of $\alpha$ until that mass is completely transported. The figure is from the book and illustrates this.


问:
$R/(a)$ is torsion for any nonzero $a \in R$?
Let $R$ be an integral domain and $a \in R$ be nonzero. The claim now is that $R/(a)$ is a torsion $R$-module, where $(a) = Ra = \{ ra: r \in R\}$ is a cyclic submodule.

I don't know why I still cannot formulate a proof. I've read Foote and Dummit and some notes I found online, all of which seems to regard it as trivial so there's got to be something small I've missed. Here's my attempt:

Attempt. We prove by contradiction. Suppose $R/(a)$ is not torsion. Then there exists $r + (a) \in R/(a)$, such that for any nonzero $s \in R$, we have
$$s \cdot (r + (a)) = sr + (a) \neq 0_R + (a).$$
Accordingly, this means that $sr \notin (a)$ and $sr \neq 0_R $. And here's where I am stuck.

I was thinking of putting it into a form where I can use that $R$ is an integral domain, but I have $rs \neq 0$ and not $rs = 0$. I have spent hours on this, so it would be helpful if someone could point me in the right direction.

答: Consider a typical element $r+(a)$. Then $a(r+(a)) = ra+(a) = 0$ as $ra \in (a)$.

ContentLicense: CC BY-SA 4.0


问:
Fourier transform of a tempered distribution : why a link with classical Fourier transform?
Fourier transform ($F$) of tempered distribution $\operatorname{sinc}$ is tempered distribution $\operatorname{Rect}$.

Does it mean that tempered distributions $F(\operatorname{sinc})$  and $\operatorname{Rect}$ behave the same as far as integration against Schwartz functions goes?

If so, how the latter (intuitively) proves that the Fourier transform (not in the sense of distributions) of $\operatorname{sinc}$ is indeed $\operatorname{Rect}$?

In other words : how does this prove that Fourier transform of $\operatorname{sinc}$ in the sense of distribution is Fourier transform of $\operatorname{sinc}$ in the sense of functions?

答:
To answer your first question: yes, when you say that two distributions are equal you mean that they behave the same when integrated against test functions.

To show that the Fourier transform of $\operatorname{sinc}$ is $\operatorname{rect}$, I would actually go the other way around: take the Fourier transform of $\operatorname{rect}$.  It's a very basic one to calculate and will yield $\operatorname{sinc}$.  Then note that $\mathcal{F}^2(f) = \tilde{f}$, where $\tilde{f} = f(-x)$.  But both $\operatorname{rect}$ and $\operatorname{sinc}$ are symmetric with respect to this reflection, thus you have your desired result.


问:
Proving that $\pi = \sum_{n=0}^{\infty} \frac{1}{16^n}\left(\frac{4}{8n+1} -\frac{2}{8n+4}-\frac{1}{8n+5}-\frac{1}{8n+6}\right)$
$$ \pi = \sum_{n=0}^{\infty} \frac{1}{16^n}\left(\frac{4}{8n+1} -\frac{2}{8n+4}-\frac{1}{8n+5}-\frac{1}{8n+6}\right)$$

I guess that using the Leibniz series could be somehow the way of the proof

$$\frac{\pi}{4}=\sum_{n=0}^{\infty} \frac{(-1)^{n}}{2n+1}=1-\frac{1}{3}+\frac{1}{5}-...$$ is it the right way of thinking?

答: Use $\int_0^1x^{n-1}dx=\frac1n$ to write your sum as$$\begin{align}&\int_0^1\sum_{n\ge0}\left(\frac{x^8}{16}\right)^n(4-2x^3-x^4-x^5)dx\\&\stackrel{\ast}{=}\int_0^1\frac{16(1-x)}{(2-x^2)(2-2x+x^2)}dx\\&=\int_0^1\left(-\frac{4x}{2-x^2}+\frac{8-4x}{2-2x+x^2}\right)dx\\&=[2\ln(2-x^2)-2\ln(2-2x+x^2)+4\arctan(x-1)]_0^1\\&=\pi,\end{align}$$where $\stackrel{\ast}{=}$ repeatedly uses the difference of two squares to take common factors out of the rational integrand (note we've summed a geometric series). That's the hard part, which you should work through yourself.


问:
Find the rotation of the object?

Image 1: The object's original height and width are 9 and 4. Here the object is not tilted, so the bounding box would cover the same dimension.

Image 2: If we tilt the object, the bounding box, as you can observe from the image, has the height and width of 10 and 8.

From this information, can we find out how much degree is the object rotated in the second image?

答:
You need to solve the system of equations

$$\begin{cases}W=w\cos\theta+h\sin\theta,\\H=w\sin\theta+h\cos\theta.\end{cases}$$

In fact a single equation is enough, and there is a compatibility condition, namely

$$W^2+H^2=w^2+h^2+2wh\sin2\theta,\\W^2-H^2=(w^2-h^2)\cos2\theta$$

and

$$\left(\frac{W^2+H^2-w^2-h^2}{2wh}\right)^2+\left(\frac{W^2-H^2}{w^2-h^2}\right)^2=1.$$

It is not really verified by your data. (By the way, the diagonal of the rectangle is $\sqrt{4^2+9^2}<10$ and the second equation is not possible.)

To solve the first equation, write

$$(W-w \cos\theta)^2=h^2(1-\cos^2\theta)$$ and solve this quadratic equation in $\cos\theta$.

Title: Find the rotation of the object?


问:
What is the definition for an infinite set?
I'm physicist, not a mathematician, but this time I have following question related to Math:
What is an infinite set per definition?
Of course I know, that a set is infinite, when it is not finite - clear.

But lets say I have infinite set M.

Assume there is a surjection $f: M \rightarrow \mathbb{N}$

So every element of $m \in M$ points to a given $n \in N$.

Such a set M must be, of course infinite, but does the definition suffice for all infinite sets, including non countable ones so I can say:

"Each infinite set has a surjection $f: M \rightarrow \mathbb{N}$" ?

For example a surjective function for the non countable infinite set $\mathbb{R^+_0}$ could be
$x \in [n-1, n) \mapsto n$

But does my definition include all possible infinite sets and is this definition reasonable at all?

Sorry for mathematical incorrectness, but I think one can understand what I mean.

答:
Yes that is sufficient as long as the map is surjective, the actual definition should be

An infinite set is a set that is not a finite set.
So you could show that there does not exist a bijection between your "infinite" set and a finite set.

Other ways:

A set is infinite if and only if for every natural number, the set has a subset whose cardinality is that natural number.

If the axiom of choice holds, then a set is infinite if and only if it includes a countable infinite subset.

Also if interested:

the actual definition of finite set is centered on the fact that you define numbers in such a way that they are sets, exactly of their cardinality, and so on... but this was not the question.

If you'd like to know more about this finite set definition just comment.


答:
Let $\theta$ be the angle that the object is rotated anticlockwise. $\theta$ is the acute angle that the $9$-side of the object makes with the vertical bound, and is also the acute angle that the $4$-side of the object makes with the horizontal bound.

Then consider the vertical side of the bounding box,

$$4 \sin \theta + 9 \cos \theta = 10$$

And consider the horizontal side of the bounding box,

$$9\sin \theta + 4 \cos \theta = 8$$

These are two linear equations in two unknows $\cos \theta$ and $\sin \theta$. Solve for them to find $\theta$.

(If the results are inconsistent that $\cos ^2\theta + \sin^2\theta \ne 1$, then the dimensions of the object or the bounding box may be wrong)

According to image 2, the vertical bounds are not tight bounds and there may be spaces above and below the object. So this section considers only the horizontal bound:

$$9\sin \theta + 4 \cos \theta = 8$$

Let $L$ be positive number and $\phi$ be an acute angle, such that $L\cos\phi = 9$ and $L\sin\phi = 4$. Solve $L$ and $\phi$ by

$$\begin{align*}
L &= \sqrt{(L\cos\phi)^2 + (L\sin\phi)^2}\\
&= \sqrt{9^2+4^2}\\
&= \sqrt{97}\\
\sin\phi &= \frac 4L\\
\cos \phi &= \frac9L\\
\end{align*}$$

The equation for the horizontal bound becomes

$$\begin{align*}
(L\cos\phi) \sin\theta + (L\sin\phi)\cos\theta &= 8\\
L\sin(\theta+\phi) &= 8\\
\sin(\theta+\phi) &= \frac 8L\\
\cos(\theta+\phi) &= \frac{\sqrt{L^2-8^2}}L= \frac{\sqrt{33}}{L}\\
\sin\theta &= \sin[(\theta+\phi)-\phi]\\
&= \sin(\theta+\phi)\cos\phi - \cos(\theta+\phi)\sin\phi\\
&= \frac 8L\cdot \frac9L - \frac{\sqrt{33}}{L}\cdot\frac{4}{L}\\
\theta &= \arcsin\frac{72-4\sqrt{33}}{97}
\end{align*}$$

The geometric meaning is that $L$ is the length of the object's diagonal, and $\phi$ is the angle between a $9$-side and a diagonal of the object.

Title: Find the rotation of the object?

Body:
Image 1: The object's original height and width are 9 and 4. Here the object is not tilted, so the bounding box would cover the same dimension.

Image 2: If we tilt the object, the bounding box, as you can observe from the image, has the height and width of 10 and 8.

From this information, can we find out how much degree is the object rotated in the second image?


答:
One could possibly use that definition, but it would be unusual. To get an understanding of cardinality we need a stronger concept than surjectivity, namely bijectivity. Two sets are said to have the same cardinality if it exists a bijection between them. This gives rise to a natural way of assigning a «size», or cardinality, to finite sets. We say that a set $A$ has cardinality $n$ if there exists a bijection $f:A \rightarrow \{ m \in \mathbb{N} \, | \, 1 \leq m \leq n \}$.

Having done this, we may define an infinite set as follows: A set $A$ is called infinite if there exists no $n \in \mathbb{N}$ so that there exists a bijection  $f:A \rightarrow \{ m \in \mathbb{N} \, | \, 1 \leq m \leq n \}$.

Title: What is the definition for an infinite set?

Body:
I'm physicist, not a mathematician, but this time I have following question related to Math:
What is an infinite set per definition?
Of course I know, that a set is infinite, when it is not finite - clear.

But lets say I have infinite set M.

Assume there is a surjection $f: M \rightarrow \mathbb{N}$

So every element of $m \in M$ points to a given $n \in N$.

Such a set M must be, of course infinite, but does the definition suffice for all infinite sets, including non countable ones so I can say:

"Each infinite set has a surjection $f: M \rightarrow \mathbb{N}$" ?

For example a surjective function for the non countable infinite set $\mathbb{R^+_0}$ could be
$x \in [n-1, n) \mapsto n$

But does my definition include all possible infinite sets and is this definition reasonable at all?

Sorry for mathematical incorrectness, but I think one can understand what I mean.


答:
Depends - how do you feel about the axiom of choice? (Or rather, very tiny fragments of it.)

In set theory without the axiom of choice (that is, $\mathsf{ZF}$ as opposed to $\mathsf{ZFC}$), the standard definition of "finite" is "in bijection with an element of $\omega$" - where $\omega$ is the smallest inductive set, that is, the smallest set with $\emptyset$ as an element and closed under the map $x\mapsto x\cup\{x\}$. Think of $\omega$ as giving a "purely $\in$-based" description of $\mathbb{N}$. Elements of $\omega$ are the finite (von Neumann) ordinals.

We also have the notion of Dedekind finiteness: a set $A$ is Dedekind-finite iff there is no injection $A\rightarrow A$ which is not a surjection (think by contrast about Hilbert's Hotel). This is equivalent to $A$ not having an injection from $\omega$ (or $\mathbb{N}$ if you prefer). You raised a third notion, namely "does not surject onto $\omega$" (this one's definitely in the literature too, I just don't recall its name at the moment - I'll add it when I can find it). And there are many others.

Over $\mathsf{ZF}$ alone, these need not be the same; e.g. it is consistent with $\mathsf{ZF}$ that there is an infinite set which is Dedekind-finite. Indeed, in $\mathsf{ZF}$ alone there is a lot to be said about the various types of finiteness. But in $\mathsf{ZFC}$ these all coincide, and so in particular your proposed definition works ... if you're happy assuming (at least a small fragment of) the axiom of choice.


问:
Can I write the Taylor series of some function $f(x)$ around $x=1$ as: $f(x)=\sum_{n=1}^{\infty} a_n (x-1)^{2n-1}.$
Can I write the Taylor series of some function $f(x)$ around $x=1$ as:

$$f(x)=\sum_{n=1}^{\infty} a_n (x-1)^{2n-1}.$$

Thnx.

答:
Yes, you can. As given, it means that

$$a_k=\begin{cases}0,&k\;\text{is even}\\{}\\a_{2n-1},& k=2n-1\;\text{ is odd}\end{cases}$$


答:
A proof assuming AC goes as follows:

If $M$ is not finite, then construct inductively a sequnce $m_i \in M$ of distinct elements. This works, because $M \setminus \{m_1, \dots, m_i\}$ is never empty, otherwise $M$ would be finite. Any map $M \to \mathbb N, m_n \mapsto n$ that maps elements $M \setminus \{m_1, \dots\}$ is surjective. (To prove existence of such a map uses AC).

If $M \to \mathbb N$ is surjective, then $M$ cannot be finite, since otherwise the image of this map is already finite and properly contained in $\mathbb N$.


答:
There are a couple of ways to define "infinite set", depending on your set theory, and depending on whether you want your primary concept to be that of "infinite set" or that of "finite set."

Giving primacy to finite set. We define a set $X$ to be finite if it can be put in one-to-one correspondence with a proper initial segment of $\mathbb{N}$; that is, there exists a bijection $f\colon X\to\{0,1,\ldots,n-1\}$ for some natural number $n$. A set $X$ is infinite if and only if it is not finite. The set $\mathbb{N}$ is defined as the least inductive set, and there is a very specific object in Set Theory corresponding to it.

Giving primacy to infinite sets. A set $X$ is "Dedekind infinite" if there is a proper subset $Y$ of $X$ such that $X$ and $Y$ can be put in bijective correspondence (there is a bijection $f\colon X\to Y$). A set is Dedekind-finite if and only if it is not Dedekind-infinite.

In Zermelo-Fraenkel Set Theory ($\mathsf{ZF}$), without assuming the Axiom of Choice, one can show that a Dedekind-infinite set $X$ contains a countably infinite subset; that is, there is an injection $f\colon\mathbb{N}\to X$, and conversely, any set $Y$ that admits an injection $f\colon \mathbb{N}\to Y$ is Dedekind-infinite. This definition agrees with your proposal: say $X$ is Dedekind-infinite, and let $f\colon\mathbb{N}\to X$ be an injection. Define $g\colon X\to \mathbb{N}$ as follows: given $x\in X$, if $x\notin f(\mathbb{N})$, then $g(x)=0$. If $x\in f(\mathbb{N})$, then because $f$ is one-to-one, there exists a unique $n\in\mathbb{N}$ such that $x=f(n)$; define $g(x)=n$. Then $g$ is surjective, since for every $n\in\mathbb{N}$, $g(f(n))=n$.

One can also show in $\mathsf{ZF}$ that if $X$ is Dedekind-infinite, then it is also infinite in the sense of the first definition. However, there are set theories in which there are sets that are not Dedekind-infinite and also are not finite in the sense of the first definition.

In Zermelo-Fraenkel with Choice ($\mathsf{ZFC}$), if a set is not Dedekind-infinite then it is finite in the sense of the first definition, and thus that the two definitions (finite and Dedekind-finite; infinite and Dedekind-infinite) coincide.

However, while Dedekind-infinite implies your notion even without the Axiom of Choice, your definition does not imply Dedekind-infinite if we do not have the Axiom of Choice at hand: your definition is what is called a "weakly Dedekind-infinite set", and it sits somewhere between Dedekind-infinite and finite; that is, if a set is Dedekind-infinite then it is weakly Dedekind-infinite (as noted above), and if it is weakly Dedekind-infinite then it is not finite; but you could have weakly Dedekind-infinite sets that are not Dedekind-infinite, and you could have a set that is not weakly Dedekind-infinite but is also not finite.


问:
divergence in Einstein Summation
I've learned that divergence of f in Cartesian coordinates is expressed as $\partial_if_i$ in Einstein Notation.

How would divergence in curvilinear coordinates be expressed in Einstein Notation?

$$\nabla\cdot \vec{v} =  \frac{1}{h_1h_2h_3}[ \frac{\partial (v_1h_2h_3)}{\partial u_1} + \frac{\partial (h_1v_2h_3)}{\partial u_2} + \frac{\partial (h_1h_2v_3)}{\partial u_3}]. $$

答:
I would suggest

$$\frac{1}{h_1 h_2 h_3} \partial_i \bigg( v_i \prod_{j \neq i} h_j \bigg)$$

Title: divergence in Einstein Summation


问:
Types of solutions to a partial differential operator
Suppose that the operator D in a constant-coefficient second-order partial differential equation $D\varphi = 0$ is reducible, meaning it can factored into two distinct first-order factors $D=P_1P_2$ where
$$P_i = \alpha_i \frac{\partial}{\partial x} + \beta_i \frac{\partial}{\partial y} + \gamma_i$$
with $\alpha_i, \beta_i, \gamma_i$ constants. Show that the general solution to $D\varphi = 0$ can be written in the form $\varphi = \phi_1 + \phi_2$ with $P_1\phi_1 = 0$ and $P_2\phi_2 = 0$.

Otherwise, show that the general solution of
$$ \frac{\partial^2\varphi}{\partial x \partial y} + 2 \frac{\partial^2 \varphi}{\partial y^2} - \frac{\partial \varphi}{\partial x} - 2 \frac{\partial \varphi}{\partial y} = 0$$ is $\varphi(x,y) = f(2x - y) + e^yg(x)$

Just not really sure where to start. The question overall is confusing me, and I'm not sure what to do or how to attempt it. Any help is appreciated.

答:
Note that you have that:
$$\frac{\partial^2\varphi}{\partial x \partial y} + 2 \frac{\partial^2 \varphi}{\partial y^2} - \frac{\partial \varphi}{\partial x} - 2 \frac{\partial \varphi}{\partial y} = 0$$
$$\left (\dfrac{\partial }{\partial x}+2\dfrac { \partial }{\partial y}\right)\left (\frac{\partial }{\partial y} - 1 \right) \varphi  = 0$$
$$P_1P_2 \varphi=0$$

Now you need to solve these two partial differential equations of first order:
$$1.  \, \left (\dfrac{\partial }{\partial x}+2\dfrac { \partial }{\partial y}\right)\varphi_1 = 0$$
$$2. \, \left (\frac{\partial }{\partial y} - 1 \right) \varphi_2  = 0$$
Then you have:
$$\varphi=\varphi_1+\varphi_2$$


问:
How to solve for $x$ and $y$ given these two multivariable functions?
I am trying to find the critical points of this function $(x-y)(16-xy)$

I found that the partial derivatives are $f_x = 16-2xy+y^2 = 0$ and $f_y=-x^2-16+2xy = 0$. However, I have tried everything but cannot solve for $x$ and $y$ with these two equations. How do you solve for $x$ and $y$?

答:
Note
$$2xy-y^2=16=2xy-x^2$$
which leads to $x^2=y^2$, or $x=\pm y$.


问:
Example 1.K in A User's Guide to Spectral Sequences
I'm having trouble with Example 1.K, p.25, of John McCleary's book A User's Guide to Spectral Sequences.

Specifically, I don't understand how he defines the "obvious map" in the second paragraph :
  $$\text{"Notice that there is an obvious mapping from $A^*$ to $H^*$ since $A^*$ is free."}$$

It seems to me such a mapping would involve arbitrary choices because the isomorphism we are given is between quotients, and that it would be non trivial wether these choices could be made in such a way as to give a map of algebras.

答: I resolved my confusion : it's a straightforward application of the universal property of the free graded-commutative graded algebra on a graded set of generators. My confusion stemmed from the fact that I hadn't really understood that the filtration on $H^*$ was used to filter each factor $H^n$, and that any indeterminacy in choosing representatives of elements in $$E^{p,q}_0=\frac{F^pH^{n}}{F^{p+1}H^{n}}$$ (where $n=p+q$) would remain within $H^n$ so be of given degree, and especially given parity. Someow I thought that the indeterminacy could cause one to choose representatives in a sum of different $H^m$...</p>

ContentLicense: CC BY-SA 3.0


问:
Prove that the $24\Big\lfloor\frac{p+3}{6}\Big\rfloor p+1=n^2$ for any prime p
Have met an experimental result, that for any prime p:

$$24\Big\lfloor\frac{p+3}{6}\Big\rfloor p+1=n^2$$

Where
$$n \equiv\pm 1\pmod {12}$$

The last rule is true for any solution of the first equation even for nonprime $p$.

I was trying to prove this using possible forms of primes such as $p\equiv 1,3,5,7,11\pmod {12}$. But either I am doing something wrong or this is not the right way can not reach the final result.

答:
If $p = 6k+1$, then your expression is just:

$$24\cdot k\cdot(6k+1) + 1 = 144k^2+24k+1 = (12k+1)^2.$$
You can do a similar thing for when $p = 6k-1$ and the only other possibility is $p = 2.$


问:
Axiom of Choice to build a set of real numbers not Lebesgue measurable
below is an extract of the book (at the very beginning) of "The Axiom of Choice" by Jech. I am having a hard time at understanding this introductory example, that shows how to construct a set of real numbers not Lebesgue measurable, using the axiom of choice :

The thing I'm particularly confused with is the fact that the equivalence relation is defined for $x, y$ both in $[0,1]$, but yet he seems to assign any real number to the equivalence classes. How can he define something only on $[0,1]$ and assert (but I might be wrong):

$$\mathbb{R} = \{ [y] : y \in [0,1]\} = \left\{ \{y + r : r\in \mathbb{Q}\} : y \in [0,1]\right\}$$

The last part also is not that obvious to me. Isn't it wrong to say:

$$\left\{ \{y + r : r\in \mathbb{Q}, 0\leq r \leq 1 \} : y \in [0,1]\right\} \subset [0,1]$$

Thanks for your help

EDIT

Ok I understand some things more:

$$\forall x \in \mathbb{R}, x - \lfloor x \rfloor \in [0, 1]$$

and then there exists a unique rational $r' \in [0,1]$  and a unique real $y \in [0,1]$ such that $x = y + \underbrace{r' + \lfloor x \rfloor}_{r\in\mathbb{Q}}$.

Then:
$$\begin{align}
\mu(\mathbb{R}) &= \mu(\bigcup\limits_{r\in\mathbb{Q}} M_r) \\
&= \sum_{r\in\mathbb{Q}} \mu(M_r) \quad\text{ (since it's a partition)} \\
&= \sum_{r\in\mathbb{Q}} \mu(M) \\
&= +\infty . \mu(M)
\end{align}$$

So with the convention that $+\infty.0 = 0$, I understand the first contradiction ($\mu(M) = 0$)

but I don't understand the last inequality, I don't think we have, right?:

$$\bigcup\limits_{r\in[0,1]\cap\mathbb{Q}} M_r \subset [0,1]$$

答:
He's not asserting that $\mathbb{R}$ is the union of the $\sim$-classes; as you say, that union would just be $[0,1]$.

Rather, he's saying $$\mathbb{R}=\bigcup_{r\in\mathbb{Q}}M_r,$$ where $$M_r=\{y+r: y\in M\}.$$ Note that $M_r$ is not in general a subset of $[0,1]$ - consider e.g. $M_{17}$.

Your second question runs into the same issue.


问:
Eigenvalues of strange matrix
I have a rather weird square matrix, $M_n$, that is of dimension $n$. That's the best I can explain it, I think. It has a general form, and I think it's best to just show some examples

$$
M_3 = \begin{pmatrix}
1 & -1 & 1\\
-1 & 2 & -2\\
1 & -2 & 3
\end{pmatrix},
$$

$$
M_4 = \begin{pmatrix}
1 & -1 & 1 & -1\\
-1 & 2 & -2 & 2\\
1 & -2 & 3 & -3\\
-1 & 2 & -3 & 4
\end{pmatrix},
$$

$$
M_5 = \begin{pmatrix}
1 & -1 & 1 & -1 & 1\\
-1 & 2 & -2 & 2 & -2\\
1 & -2 & 3 & -3 & 3\\
-1 & 2 & -3 & 4 & -4\\
1 & -2 & 3 & -4 & 5
\end{pmatrix}.
$$

As you can see in each column/row the sign changes for each element, and for the $i^{th}$ row/column, the $i^{th}$ to the $n^{th}$ elements all have norm $i$. I don't know if it's any use explaining it further, as the form becomes pretty clear from the examples given. My question is, has anyone seen something like this and does anyone know if there's a way of calculating the eigenvalues?

答:
The eigenvalues are the roots of the characteristic polynomial.  This is irreducible over the rationals in many cases ($n =  1, 2, 3, 5, 6, 8, 9, 11, 14, 15, 18, 20, 21, 23, 26, 29, 30, \ldots$), so in general I think there is no simple formula for them.  The characteristic polynomials (call them $C_n(\lambda)$) appear to satisfy the recurrence

$$  C_{n+2}(\lambda) = (2\lambda-1) C_{n+1}(\lambda) - \lambda^2 C_n(\lambda)$$
with $C_1(\lambda) = \lambda - 1$, $C_2(\lambda) = \lambda^2 - 3 \lambda + 1$.

$1$ is an eigenvalue if and only if $n \equiv 1 \mod 3$.

Title: Eigenvalues of strange matrix


答:
This is an interesting question, because we can interpret it as asking if there is any infinite cardinality strictly smaller than $\aleph_0$.

Infinite sets are usually defined in terms of finite sets. A set is finite if there is a one-to-one mapping between it and a set of the form $\boldsymbol n = \{0, 1, ..., n\}$ for some $n\in \mathbb{N}$.

So this interesting question is, is there any set which satisfies the standard definition but does not have a surjection onto $\mathbb{N}$?

Let's try to show that.

Let us suppose we have a set $S$ such that for every $n\in \mathbb N$ there is no one-to-one mapping $f:S\to \boldsymbol n$.

First we note that at the very least, for every $n\in \mathbb N$ we will always be able to find at least a surjective $g_n:S\to \boldsymbol n$.

We can show this by induction. The base case for $n=0$ is trivial. Suppose that there is a surjective $g_n:S\to \boldsymbol n$. Since we assumed that there are no one-to-one mappings between $S$ and $\boldsymbol n$, there must be two elements $a_n,b\in S$ such that $g_n(a) = g_n(b)$. Hence we can define $g_{n+1}(x) = g_n(x)$ if $x\not = a$ and $g_{n+1}(a) = n+1$.

Ok so now we have a surjection $g_n: S \to \boldsymbol n$ for every $n$. Not only that, but we have also defined along the way a series $A = \{a_0, ..., a_n\}$ such that $g_n(a_n)=n$ for every $n$.

Let us define $g:S \to \mathbb N$ such that $g(a_n) = n$ ($g(x) = 0$ if $x \not\in A$.

Hence we have defined a surjection $g:S \to \mathbb N$, and thus we have seen that any infinite set satisfying the classical definition also satisfies that there is a surjection between it and the natural numbers.

PS: I am 78% sure that this construction relies on the axiom of choice, but right now I cant see exactly how.


问:
Bound of iterations for Jacobi / Gauss - Seidel / SOR
Given a linear system of equations there is the standard way to solve it by applying one of the iterative methods mentioned in the title like this :

$$ x^{k+1} = G*x^k + c$$

where $G$ is the iterative matrix whose spectral radius should be less than one for the method to converge.

Given that the condition above stands how can one calculate the upper/lower bound of iterations needed when it comes to Jacobi / GS / SOR for a specific tolerance say $0.5*10^{-6}$?

Does it have something to do with the fact that : $$\frac{||e^k||_a}{||e^0||_a}\le ||G^k||_a$$ where $a =1 ,2,\infty$ and $e^x$ refers to the $x_{th}$ error

答:
These methods correspond to the application of the fixed point method to the problem $x = G x + c$. This gives you estimates like
$$
\| x^{(k)} -z\| \leq L^k \|x^{(0)}-z\|
$$

or

$$
\| x^{(k)} -z\| \leq \frac{L^k}{1-L}\|x^{(1)}-x^{(0)}\|
$$

where $L$ is the Lipschitz constant for the iteration function, which can be bounded by the norm of the Jacobian matrix, in this case $\|G\|$.

So the answer is yes, it does have something to do with the inequality you mention, although the a posteriori estimates are more convenient, unless you have some specific bound on $\|e^{(0)}\|$.


问:
$\begin{align}&(x\! -\! a,f_1(x),\ldots,f_r(x))\\ =\ &(x\! -\! a,f_1(a),\ldots,f_r(a))\end{align}\ $ [Ideal evaluation = mod reduction]
$\begin{align}&(x\! -\! a,f_1(x),\ldots,f_r(x))\\[.1em] =\ &(x\! -\! a,f_1(a),\ldots,f_r(a))\end{align}\ $  [Ideal evaluation = mod reduction]

I am solving Aluffi chapter 0. I am completely stuck on this question.

Let R be a commutative ring, $a \in R$, and $f_1(x),\ldots, f_r(x) \in R[x]$.

Prove the equality of ideals

$(f_1(x),\ldots,f_r(x),x - a) = (f_1(a),\ldots,f_r(a),x - a)$

Prove the useful substitution trick
$\frac{R[x]}{(f_1(x),\ldots,f_r(x), x - a)} \cong \frac{R}{(f_1(a),\ldots,f_r(a))}$

答:
Hint:

You can divide each polynomial by $x-a$, obtaining
$$f_k(x)=q_k(x)(x-a)+f_k(a),\quad k=1,\dots,r.$$


问:
Show that the intersection of $\overline{\text{span }\{e_{2n}\}}$ and $\overline{\text{span }\{e_{2n}+\frac{1}{n+1}e_{2n+1}\}}$ is zero.
Let $(e_n)_{n\in\mathbb{N}}$ be a complete orthonormal system in a Hilbert space $H$. Let $x_n=e_{2n}$ and $y_n=x_n + \frac{1}{n+1}e_{2n+1}$. Let $F=\overline{\text{span }\{x_n, n\in\mathbb{N}\}}$ and $G=\overline{\text{span }\{y_n, n\in\mathbb{N}\}}$.

I need to show that any element in $F+G=\{z\in H \mid z=x+y,\quad x\in F, y\in G\}$ can be written as an element from $F$ and an element from $G$ in only one way.

When the intersection of $F$ and $G$ is the zero vector space, I can prove the statement above, but I do not know how to show $F\cap G=\{0\}$.

This means that no element in $F$ is in $G$ and vice versa.

What bothers me is that my intuition makes me feel like the intersection is not zero since $y_n = x_n + \frac{1}{n+1}e_{2n+1}$ converges to $x_n$ as $n$ becomes infinitely large, since the norm of $e_k$ is always 1. Therefore this would make it seem that $y_n=x_n\in G$ for $n\to\infty$, so $F\cap G\supset\{0,x_n\}\neq\{0\}$.

Any ideas? I know that if $z=(x+y)\in H$, then $(x+y)=\Sigma \langle (x+y)\mid e_k\rangle e_k$, since $(e_k)$ is a complete orthornormal system in $H$.

答:
It is demonstrated that $F$ and $G$ intersect trivially, as prompted in the title.

$F,G\subset H$ are closed subspaces, hence Hilbert spaces in their own.
An ONB in $F$ is $\{e_{2k}, k=0,1,2,\dots\}$, and in $G$ consider the ONB  $\big\{f_{2k}=\gamma_k\big(e_{2k}+\frac1{k+1}e_{2k+1}\big), k=0,1,\dots\big\}$ with normalisation factors $\,\gamma_k = \frac{k+1}{\sqrt{(k+1)^2+1}}$.

Let $z$ like "zero" be in $F\cap G$, and let
$$\sum_{k=0}^\infty\alpha_k e_{2k}\,=\; z \;=\,\sum_{k=0}^\infty\beta_k f_{2k}$$
be the Fourier expansions of $z$ in $F$ and $G$, respectively.

Denote the partial sums by $\,a_n=\sum_{k=0}^n\alpha_k e_{2k}\,$ and
$\,b_n=\sum_{k=0}^n\beta_k f_{2k}$, they converge in norm to $z$.

Fix $\varepsilon>0$. Then choose $N$ such that both
$\,\|b_n-z\|,\|z-a_n\|< \frac{1}{2}\sqrt\varepsilon\,$ for all $n\geqslant N$.
Then $\|b_n-a_n\|<\sqrt\varepsilon\,$ by the triangle inequality, and
$$\begin{align}\varepsilon \;>\;\|b_n-a_n\|^2 & \;=\;
\Big\|\sum\nolimits_{k=0}^n\big(\beta_k\gamma_k\, e_{2k}
 + \beta_k\frac{\gamma_k}{k+1}e_{2k+1} - \alpha_k e_{2k}\big)\Big\|^2 \\[1ex]
 & \;=\;\sum_{k=0}^n\Big(|\beta_k\gamma_k- \alpha_k|^2 + |\beta_k|^2\frac{\gamma_k^2}{(k+1)^2}\Big)\end{align}$$
as $\{e_0,e_1,\dots,e_{2k},e_{2k+1},\dots\}$ is an ONB in $H$.

Now in the last sum each summand $<\varepsilon$ by necessity, and $\varepsilon>0$ was at choice. Hence $\beta_k=0\,$ for all $k$, which means $z=0$ and $F\cap G=\{0\}\,.
\qquad\square$


问:
Amount of linearly independent vectors and linear subspaces in a vector space
Let K be a finite field with q elements and V an n-dimensional vector space with k $\in$ ℕ and k≥1. For 1≤k≤n I want to show that there are
$$\prod_{i=0}^{k-1} (q^n-q^i)$$
k-tupels of linearly independent vectors
and
$$\prod_{i=0}^{k-1} (\tfrac{q^{n-1}-1}{q^{k-1}-1})$$
k-dimensional linear subspaces of V.

答:
Here is my derivation:

$$(i)$$
Step 1: Showing that a vector space $V$ of dimension n over the finite field
$K$ has $p^n$ elements.

Since $V$ is a vector space of dimension $n$, there is a basis $B = \{\ e_2, ... , e_n \}$ with $n$ elements. Every element $v \in V$ now has a (unique) representation as a linear combination $\sum_{k=1}^{n} \lambda_ie_i$ with coefficients from the
field $K$. For each of the $n$ basis vectors $e_i$ one then has $q$ possibilities
to choose a coefficient. In total one obtains $q^n$ different
elements. $\square$

Step 2: Amount of $k$-tupels in general.

First the number of $k$-tuples of linearly independent vectors: For the first vector one can choose any element $v \neq 0$ from $V$, which means that there are $q^n-1$ possibilities.
The second vector cannot be a multiple of the first: $q^n-q$ possibilities. The third vector must not
lie in the product of the first two: $q^n-q^2$
For
the last vector we receive $q^n-q^{k-1}$ possibilities.

Step 3: Combination of all possibilities.

So there is a total of $$\prod_{i=1}^{k} (q^n-q^{i-1})$$ k-tuples. Now in order to get the given equation we shift the indices.

Notice that
$$\prod_{i=1}^{k} (q^n-q^{i-1})=(q^n-q^{1-1})\cdot(q^n-q^{2-1})\cdot...\cdot(q^n-q^{k-1})=\prod_{i=0}^{k-1} (q^n-q^{i})$$
Thus we get the hypothesis. $\square$

$$(ii)$$ The linearly independent systems generate the subspace but since the basis is not unique one has to divide by the number of bases which is $(q^k-1)\cdot(q^k-q)\cdot...\cdot(q^k-q^{k-1})$.

This gives us
$$\prod_{i=0}^{k-1} \tfrac{q^n-q^{i}}{q^k-q^{i}}=\prod_{i=0}^{k-1} \tfrac{q^n-q^{i}}{q^k-q^{i}}\cdot\tfrac{q^{-i}}{q^{-i}}=\prod_{i=0}^{k-1} \tfrac{q^{n-i}-1}{q^{k-1}-1}$$
which is our hypothesis. $\square$


问:
Finding the supremum of a product of the difference between complex number of modulus one.
I would like to have some help on the following problem:
Let $T=\{ z\in  \mathbb{C}~ |~|z|=1\}$ and $n\geq 2$ a positive integer. Find :

$$ \sup_{(z_{1},\cdots , z_{n}) \in T^{n}} (\Pi_{ 1 \leq j \neq k \leq n }  |z_{j}-z_{k}|)^{\frac{1}{n(n-1)}} $$

The progress I maid so far is the following :
Let $z_k=e^{2\pi ia_k}$.
$|z_j-z_k|=|e^{2\pi ia_j}-e^{2\pi ia_k}|=\\ =|\cos{(2\pi a_j)}-\cos{(2\pi a_k)}+i\sin{(2\pi a_j)}-i\sin{(2\pi a_k)}|=\\
=2|\sin{(\pi (a_j-a_k))}|$
$(\prod_{ 1 \leq j \neq k \leq n } |z_{j}-z_{k}|)^{\frac{1}{n(n-1)}}=\left(\prod_{1\leq j\neq k \leq n}2|\sin{(\pi (a_j-a_k))}|\right)^{\frac{1}{n(n-1)}}=\sqrt{2}\left(\prod |\sin{(\pi (a_j-a_k))}|\right)^{\frac{1}{n(n-1)}}$

Then I don't know how to continue. The maximum value of $x \to |\sin(x)|$ is $1$ so I need to find a combinaison of $a_{k}$  such that $|\sin(\pi (a_{j}-a_{k}))|=1$. I need $a_{j}-a_{k}$ to always be in the form $\frac{2m+1}{2}$

答:
Given $n$, we show that the required supremum $s_n=n^{\tfrac 1{n-1}}$.

Given any $(z_{1},\cdots , z_{n}) \in T^{n}$ let $Z=\| z_{ij}\|$ be an $n\times n$ Vandermonde matrix such that $z_{ij}=z_j^{i-1}$ for each $i,j\in 1,\dots, n$. Then

$$\prod_{ 1 \leq j \neq k \leq n }  |z_{j}-z_{k}|=|\det Z|^2.$$

By Hadamard's determinant bound,
$|\det Z|\le n^{n/2}$. That is $s_n\le (n^{n})^{{\tfrac{1}{n(n-1)}}}=n^{\tfrac 1{n-1}}.$

On the other hand, put $\xi=e^{2\pi i/n}$ (here $i$ its the imaginary unit) and $z_i=\xi^{i-1}$ for each $i=1,\dots, n$. Then

$$|\det Z|^2=\left|\prod_{ 1 \leq j \neq k \leq n }  (z_{j}-z_{k})\right|=\left|\prod_{ 1 \leq j \neq k \leq n }  (\xi^{j-1}-\xi^{k-1})\right|=$$
$$\left|\prod_{ 1 \leq j \neq k \leq n }  (1-\xi^{k-j})\right|=\left|\prod_{m=1}^{n-1}  (1-\xi^m)^{n}\right|=|p(1)^n|,$$

where $p$ is a monic polynomial of $(n-1)$-th degree whose roots are $\xi^1,\dots, \xi^{n-1}$. That is $p(x)=\tfrac {x^{n}-1}{x-1}=\sum_{m=0}^{n-1} x^m$. So $p(1)=n$  and $|\det Z|^2=n^n$, which follows $s_n\ge n^{\tfrac 1{n-1}}$.


问:
Rank of the quotient of an Abelian group by its torsion part?
Let $G$ be an Abelian group, and let $G_T$ be the torsion part of $G$.  Then my question is, does the rank of $G$ always equal the rank of the quotient group $\frac{G}{G_T}$?  Or can they differ in rank?

If they’re not equal in general, are there special cases that guarantee them to be equal?

答:
Yes, it is the same.  I found the answer in this Wikipedia article:

The set of all torsion elements is a subgroup, called the torsion subgroup and denoted T(A). A group is called torsion-free if it has no non-trivial torsion elements. The factor-group A/T(A) is the unique maximal torsion-free quotient of A and its rank coincides with the rank of A.


问:
Formula for $\sum_{j=1}^{\infty} a^{|j-k|}/j$
I'm looking at finding a formula (or an approximation) for the following sum:

$$ S_{k} = \sum_{j=1}^{\infty} \frac{a^{|j-k|}}{j}$$
where it is known that $|a|<1$. This series seems to converge, but I'm not sure how to handle the power shift of $|j-k|$.

Are there known results for similar formulas?

Body:
$\begin{array}\\
S_{k}
&= \sum_{j=1}^{\infty} \dfrac{a^{|j-k|}}{j}\\
&= \sum_{j=1}^{k-1} \dfrac{a^{|j-k|}}{j}+\sum_{j=k+1}^{\infty} \dfrac{a^{|j-k|}}{j}\\
&= \sum_{j=1}^{k-1} \dfrac{a^{k-j}}{j}+\sum_{j=k+1}^{\infty} \dfrac{a^{j-k}}{j}\\
&= a^k\sum_{j=1}^{k-1} \dfrac{a^{-j}}{j}+a^{-k}\sum_{j=k+1}^{\infty} \dfrac{a^{j}}{j}\\
&= a^k\sum_{j=1}^{k-1} \dfrac{a^{-j}}{j}+a^{-k}\sum_{j=k+1}^{\infty} \dfrac{a^{j}}{j}\\
\end{array}
$

These are both partial sums
of
$-\ln(1-z)
=\sum_{j=1}^{\infty} \dfrac{z^j}{j}
$.
Wolfy uses the
Hurwitz Lerch transcendent.


问:
Irrationality of $ \frac{1}{\pi} \arccos{\frac{1}{\sqrt{n}}}$
This paper arxiv.org/pdf/0911.1933 discusses, regarding the irrationality of certain trigonometric functions. Recently, i encountered this problem which says states the given function, $$ f(n)=\frac{1}{\pi} \arccos{\frac{1}{\sqrt{n}}}$$ is irrational for every odd $n \geq 3$. But i couldn't find the proof anywhere. Can anyone provide me with the proof.</p>

答:
If you want to prove that a certain angle is irrational with respect to $\pi$, most of the times it follows from the following simple result:

Lemma: If $n, k \in {\mathbb Z}$ and $n>0$ then $2 \cos( \frac{k \pi}{n})$ is an algebraic integer.

Proof: We show that there exists a $P_n \in {\mathbb Z}[x]$ monic of degree $n$ so that

$$2 \cos(nx) = P_n(2 \cos(x)) (*) \,.$$

$P_0(X)=1, P_1(X)=X$ and using

$$\cos((n+1)x)+ \cos((n-1)x)=2 \cos(x) \cos(nx) \,,$$

we get the recurence:

$$P_{n+1}(x) = XP_n(x)-P_{n-1}(X) \,.$$

Now $(*)$ follows by induction, and then Lemma follows immediately.

Now, back to the problem. Suppose by contradiction $\frac{1}{\pi} \arccos{\frac{1}{\sqrt{n}}}$ is rational. Then we can find $n, k \in {\mathbb Z}$ and $n>0$ so that

$$\frac{1}{\pi} \arccos{\frac{1}{\sqrt{n}}}=\frac{k}{n} \,.$$

Hence

$$\frac{1}{\sqrt{n}}= \cos(\frac{2k}{n}) \,.$$

Then, by Lemma, $2\frac{1}{\sqrt{n}}$ is an algebraic integer, and hence is its square.
But then $\frac{4}{n}$ is an algebraic integer and rational, thus integer.

This shows that $4$ divides $n$.

OwnerDisplayName: anonymous

ContentLicense: CC BY-SA 2.5


问:
How to solve this line integral?
I have this line integral $\int_{C}(x^2+y^2)ds$, where $C=\{(x,y)|x^2+y^2=ay\}$. I tried solving it by substituting the variables as $x=r\cos{t}$ and $y=r\sin{t}$. So when I differentiate, I get $dx=-r\sin{t}$ and $dy=r\cos{t}$.

So popping this into the integral we get:

$\int_{C}((\cos{t})^2+(\sin{t})^2)*\sqrt{(-r\sin{t})^2+(r\cos{t})^2}dt$

I could probably integrate this if I knew how to apply the given circle.

答:
If $x=r\cos t$ and $y=r\sin t$, then $x^2+y^2=r^2\ne ay$; besides, what is $r$?

Instead, since$$x^2+y^2=ay\iff x^2+\left(y-\frac a2\right)^2=\frac{a^2}4,$$you should take $x=\frac a2\cos t$ and $y=\frac a2+\frac a2\sin t$. And then you compute$$\int_0^{2\pi}\left(\frac{a^2}4\cos^2t+\frac{a^2}4(1+\sin t)^2\right)\left\|\left(-\frac a2\sin t,\frac a2\cos t\right)\right\|\,\mathrm dt.$$

Title: How to solve this line integral?


问:
Inner product matrix
Let A $\epsilon$ $\mathcal M_n$. Define in $\mathbb {R^n}$x$\mathbb {R^n}$:

$\langle$x,y$\rangle_A$=$\langle$Ax,Ay$\rangle$

Prove that $\langle \rangle_A$ is an inner product in $\mathbb R^n$, if and only if, A is invertible. (In the right side on the equation, we have the canonical inner product in $\mathbb R^n$)

答: If $A$ is not invertible the null space of $A$ is not just $\{\vec{0}\}$. Therefore $<x, x>_A$ will be 0 for every element in the nullspace of $A$, which is not prohibited by definition of an inner product.

Title: Inner product matrix


问:
If $f_{n}$ has a dense image, then $\bigcap (f_{1}\circ\cdots\circ f_{n})(X_{n})$ is dense
Let $\{(X_{n}, d_{n})\}_{n\in\mathbb{N}}$ be a sequence of complete metric spaces and $\{f_{n}: X_{n}\to X_{n − 1}\}_{n\in \mathbb{N}}$ a sequence of continuous functions. If $f_{n}$ has a dense image for each $n\in \mathbb{N}$, show that $\bigcap_{n\in \mathbb{N}}(f_{1}\circ f_{2}\circ \cdots \circ f_{n}) (X_{n})$ is dense at $X_{0}$.

My attemps:
if $f_{n}$ has a dense image then $\overline{f_{n}(X_{n})}=X_{n-1}$ I want to show that
$$\overline{\bigcap_{n\in \mathbb{N}}(f_{1} \circ f_{2} \circ \cdots \circ f_{n})(X_{n})} = X_{0}. $$
Let $F_{n}=(f_{1}\circ f_{2} \circ \dots ◦ f_{n})(X_{n})$. By induction, I see that $F_{n+1} ⊆ F_{n} ⊆ X_{0}$. Indeed, if $n=1$, then
$$F_{2}=(f_{1}\circ f_{2})(X_{2})=f_{1}(f_{2}(X_{2}))\subseteq f_{1}(\overline{f_{2}(X_{2}}))=f_{1}(X_{1})=F_{1}$$
if we assume that $F_{k+1}\subseteq F_{k}\subset X_{0}$. Then,
$$F_{k+2} = (f_{1} \circ f_{2} \circ \cdots \circ f_{k+1} \circ f_{k+2})(X_{k+2}) = (f_{1} \circ f_{2} \circ \cdots \circ f_{k+1})(f_{k+2}(X_{k+2}))\subseteq (f_{1} \circ f_{2} \circ \cdots \circ f_{k+1})(\overline{f_{k+2}(X_{k+2})}) = (f_{1} \circ f_{2} \circ \cdots \circ f_{k+1})(X_{k+1})= F_{k+1}\subseteq F_{k}\subseteq X_{0}$$
from the above we have
$$\cdots\subseteq F_{n+1}\subseteq F_{n} \subseteq \cdots \subset F_{2}\subseteq F_{1}$$
then

$$\cdots\subseteq \overline{F_{n+1}}\subseteq \overline{F_{n}} \subseteq \cdots \subset \overline{F_{2}}\subseteq \overline{F_{1}}=X_{0}$$
then
$$\overline{\bigcap_{n\in \mathbb{N}}F_{n} }\subseteq \bigcap_{n\in \mathbb{N}}\overline{F_{n}}\subseteq X_{0} .$$

is my reasoning correct?.I've been thinking that Biare's theorem could be used, but I don't know if it's possible since $F_{n}'s$ don't necessarily open.

If it is, how could the other containment prove?. I appreciate any help

答:
Here is a slight reformulation of @supinf's answer, elucidating the skipped parts:

Setting. For $0 \leq i \leq j$, define the function $f^{i\leftarrow j} $ by the composition

$$ X_i \stackrel{f^{i\leftarrow j}}{\longleftarrow} X_{j}
\quad = \quad
X_i \stackrel{f_{i+1}}{\longleftarrow} X_{i+1} \stackrel{f_{i+2}}{\longleftarrow} \cdots  \stackrel{f_j}{\longleftarrow} X_j, $$

i.e.,

\begin{align*}
f^{i\leftarrow j}
:= \begin{cases}
f_{i+1} \circ \dots \circ f_{j}, & \text{if $i < j$}, \\
\operatorname{id}_{X_j}, & \text{if $i = j$}.
\end{cases}
\end{align*}

In particular, note that $f^{j \leftarrow j+1} = f_{j+1}$ and $f^{i\leftarrow j} \circ f^{j \leftarrow k} = f^{i \leftarrow k}$. Using this, OP's question boils down to showing that

$$ \bigcap_{j\geq 0} f^{0\leftarrow j}(X_j) $$

is dense in $X_0$. We establish by showing that in fact the following subset

$$ X^{0\leftarrow} := \biggl\{ z_0 \in X_0 : \text{$\exists$ $\{z_j\}_{j\geq 0} \in \prod_{j\geq 0}X_j$ s.t. $z_j = f_{j+1}(z_{j+1})$ for all $j \geq 0$} \biggr\} $$

is dense in $X_0$.

(Note. It is clear that $X^{0\leftarrow} \subseteq \bigcap_{j\geq 0} f^{0\leftarrow j}(X_j)$. What is not clear to me is whether they coincide or not.)

Proof. Fix any open ball $B(x_0,\epsilon) \subseteq X_0$. Then we construct a sequence $\{x_n\}_{n\geq 0}$ recursively as follows:

Suppose $ x_n \in X_n $ has been chosen. Since $f_{n+1}(X_{n+1})$ is dense in $X_{n}$, we can find a sequence $\{y_k\}_{k\geq 1}$ in $X_{n+1}$ such that

$$\lim_{k\to\infty} f_{n+1}(y_k) = x_{n}.$$

Then for each $j = 0, \dots, n$, by continuity of $f^{j\leftarrow n}$ and $d_j(\cdot, \cdot)$, we have

$$ \lim_{k\to\infty} d_j\bigl( f^{j\leftarrow n}(x_n), f^{j\leftarrow n}(f_{n+1}(y_k)) \bigr) = 0. $$

From this observation, we can pick $x_{n+1} \in X_{n+1}$ so that

$$ d_j\bigl( f^{j \leftarrow n}(x_n), f^{j \leftarrow n+1}(x_{n+1}) \bigr) < \epsilon 2^{-n-1} $$

for each $0 \leq j \leq n$.

Schematically, $x_n$'s are chosen as:

Now we make several observations:

By the construction, for each $j \geq 0$, the sequence $\{ f^{j\leftarrow n}(x_n) \}_{n = j}^{\infty}$ is Cauchy in $X_j$, and so,
$$ z_j := \lim_{n\to\infty} f^{j\leftarrow n}(x_n) $$
exists in $X_j$.

For each $j \geq 0$, we have
$$ z_j
= \lim_{n\to\infty} f^{j\leftarrow n}(x_n)
= \lim_{n\to\infty} f_{j+1}(f^{(j+1)\leftarrow n}(x_n))
= f_{j+1}(z_{j+1}). $$
In particular, $z_0 \in X^{0\leftarrow}$.

We have
\begin{align*}
d_0(x_0, z_0)
&= \lim_{N\to\infty} d_0(x_0, f^{0\leftarrow N}(x_N)) \\
&\leq \lim_{N\to\infty} \sum_{n = 0}^{N-1} d_0(f^{0\leftarrow n}(x_n), f^{0\leftarrow n+1}(x_{n+1})) \\
&< \sum_{n = 0}^{\infty} \epsilon 2^{-n-1} \\
&= \epsilon,
\end{align*}
and so, $z_0 \in B(x_0, \epsilon)$.

This proves that $B(x_0, \epsilon) \cap X^{0\leftarrow} \neq \varnothing$ for any open ball $B(x_0, \epsilon)$ in $X_0$, establishing the desired claim.


问:
Is the answer for $\lvert z-1\rvert = \lvert z+1\rvert , z = 0 + iy$ and are my steps correct?
For an exercise with complex numbers we have to find all the z $\epsilon$   $\mathbb{C}$ with $\lvert z-1\lvert$ = $\lvert z+1\lvert$... I get this and want to check if it is correct:

$ z = x + iy$

$\lvert (x+iy) -1\lvert$ = $\lvert (x+iy) +1\lvert$

$\lvert (x-1)+iy\lvert$ = $\lvert (x+1)+iy\lvert$

$\sqrt{(x-1)^2+y^2}$ = $\sqrt{(x+1)^2+y^2}$

$\sqrt{x^2-2x+1+y^2}$ = $\sqrt{x^2+2x+1+y^2}$

$x^2-2x+1+y^2 = x^2+2x+1+y^2$

$-2x = 2x$

$0 = 4x$

$x = 0$

With this $\lvert z-1\lvert$ = $\lvert z+1\lvert$ would be right for all

$z = 0+iy$

Is that correct and could one simplify the answer? Thank you in advance!

答:
HINT

You can also think about it geometrically.

The complex numbers $z\in\mathbb{C}$ satisfying $|z - 1| = |z - (-1)|$ are precisely those which are at the same distance from the points $(-1,0)$ and $(1,0)$. This is the same set as the ordinate axis.


问:
How to prove this problem about functions of a complex variable?
Let $\phi_{n}$ : ${\bf C}$\{0} $\rightarrow$ ${\bf C}$ be the analytic function
$$
\phi_n(z) = 1+ \frac{1}{z}+ \frac{1}{2!z^2}+ \cdots +\frac{1}{n!z^n}.
$$
Let $M>0$ be given. How to show that for sufficiently large n, all the zeros of $\phi_n(z)$ lie in the disc {$z: |z|<M$}.

答:
Let $f_n(w)=\phi_n(1/w)=1+ \frac{w}{1}+ \frac{w^2}{2!}+ \cdots +\frac{w^n}{n!}$ for all $w$ complex; now a root $z_0$ of $\phi_n$ corresponds to a root $w_0=1/z_0$ of $f_n$ and clearly $f_n(0)=1$ so we do not worry about that.

But now $f_n(w)$ converges uniformly on compact sets to $e^w$ which has no zeroes, so in particular given a compact set $K$, there is $n(K)$ st all the zeroes of $f_n$ are outside $K$ for $n \ge n(K)$ (as otherwise an accumulation point for them in $K$ would give a zero of $e^w$).

Applying this with $K$ the compact set $|w| \le 1/M$ gives the required result!


问:
P-NP for decision problems
The final quiz problem asked whether the statement

For decision problems L1, L2 in NP, if P is not NP, L1 is at least as hard as L2, and L2 is at least as hard as L1, then L1 and L2 are NP-complete

is true or false. In fact, it seemed to me even hard to provide a counterexample for this statement, since this is intuitively a wrong assumption, but hard to prove it. I would be welcomed to know your any ideas for this problem.

答:
It could be that $L1$ and $L2$ are in $P$ (since $P\subset NP$).

Then both are equally hard but neither is $NP$-complete (since $P \ne NP$ by assumption).

Hence the statement is false.

Title: P-NP for decision problems


答:
You could divide so that there is only one absolute value. It's clear that $z=1$ is not a solution, so the equation is the same as $$1=\left\lVert\frac{z+1}{z-1}\right\rVert$$ and now to just have one "$z$":
$$1=\left\lVert1+\frac{2}{z-1}\right\rVert$$
So $1+\frac{2}{z-1}=e^{it}$. And you can use basic algebra to solve for $z$ and have a set of solutions as $t$ varies in $(0,2\pi)$. (I left out $t=0$ because that case gives no solution for $z$.)

Title: Is the answer for $\lvert z-1\rvert = \lvert z+1\rvert , z = 0 + iy$ and are my steps correct?

Body:
For an exercise with complex numbers we have to find all the z $\epsilon$   $\mathbb{C}$ with $\lvert z-1\lvert$ = $\lvert z+1\lvert$... I get this and want to check if it is correct:

$ z = x + iy$

$\lvert (x+iy) -1\lvert$ = $\lvert (x+iy) +1\lvert$

$\lvert (x-1)+iy\lvert$ = $\lvert (x+1)+iy\lvert$

$\sqrt{(x-1)^2+y^2}$ = $\sqrt{(x+1)^2+y^2}$

$\sqrt{x^2-2x+1+y^2}$ = $\sqrt{x^2+2x+1+y^2}$

$x^2-2x+1+y^2 = x^2+2x+1+y^2$

$-2x = 2x$

$0 = 4x$

$x = 0$

With this $\lvert z-1\lvert$ = $\lvert z+1\lvert$ would be right for all

$z = 0+iy$

Is that correct and could one simplify the answer? Thank you in advance!


问:
What is the probability (10-faces 3D shape rolled)
In the 10-faces 3D shape:in 4 faces is written number 1, in 3 faces is written number 2, in 3 faces is written number 3. This shape is rolled 8 times. What is the probability that the face with number 3 drops 3 times, with the number 2 drops 2 times and with the number 1 drops 3 times.
I was thinking to do (3/10)^3 * (3/10)^2 * (4/10)^3 but i know that we have to put some combinations here and i’m sucked here. Please solve if you can telling all ur steps. Thank you!</p>

答:
Analytically, this is a multinomial probability. You want three 1s, two 2a and three 3s in 8 rolls, where the probabilities of 1a, 2s, and 3a are
$.4, .3, .3,$ respectively. That is,

$${8 \choose {3,2,3}}(.4)^3(.3)^2(.3)^3 =  0.0870912,$$
where the multinomial coefficient $\frac{8!}{3!\cdot 2!\cdot 4!} = 560.$

This probability can be simulated by imagining a die with ten faces
labeled $100,100,100,100,10,10,10,1,1,1$ instead of $1,1,1,1, 2,2,2, 3,3,3,$
so that the desired total on the eight rolls will be 323. In ten million
rolls of such a die we got this total  $870,670$
times for a simulated probability of $0.087067,$ which agrees with the
analytic result to the anticipated three or four-place accuracy.

```<code>die = c(100,100,100,100,10,10,10,1,1,1)
set.seed(2020)
tot= replicate(10^7, sum(sample(die,8,rep=T)))
mean(tot==323)
[1] 0.087067
</code>```

Body:
Analytically, this is a multinomial probability. You want three 1s, two 2a and three 3s in 8 rolls, where the probabilities of 1a, 2s, and 3a are
$.4, .3, .3,$ respectively. That is,

$${8 \choose {3,2,3}}(.4)^3(.3)^2(.3)^3 =  0.0870912,$$
where the multinomial coefficient $\frac{8!}{3!\cdot 2!\cdot 4!} = 560.$

This probability can be simulated by imagining a die with ten faces
labeled $100,100,100,100,10,10,10,1,1,1$ instead of $1,1,1,1, 2,2,2, 3,3,3,$
so that the desired total on the eight rolls will be 323. In ten million
rolls of such a die we got this total  $870,670$
times for a simulated probability of $0.087067,$ which agrees with the
analytic result to the anticipated three or four-place accuracy.

die = c(100,100,100,100,10,10,10,1,1,1)
set.seed(2020)
tot= replicate(10^7, sum(sample(die,8,rep=T)))
mean(tot==323)
[1] 0.087067


答:
An alternative parametrization comes from polar coordinates centered at the origin. As you can check (you can draw a picture and draw the right triangle to see this), we have the polar equation $r=a\sin\theta$, $0\le\theta\le\pi$, so you can parametrize by
$$x=r\cos\theta = a\sin\theta\cos\theta, \quad y = r\sin\theta = a\sin^2\theta, \quad 0\le\theta\le\pi.$$
Given the integrand $x^2+y^2$, this would be my choice.

Title: How to solve this line integral?

Body:
I have this line integral $\int_{C}(x^2+y^2)ds$, where $C=\{(x,y)|x^2+y^2=ay\}$. I tried solving it by substituting the variables as $x=r\cos{t}$ and $y=r\sin{t}$. So when I differentiate, I get $dx=-r\sin{t}$ and $dy=r\cos{t}$.

So popping this into the integral we get:

$\int_{C}((\cos{t})^2+(\sin{t})^2)*\sqrt{(-r\sin{t})^2+(r\cos{t})^2}dt$

I could probably integrate this if I knew how to apply the given circle.


问:
Using Lagrange multiplier to find maximum value.
The maximum value of the function $f(x, y) = xy$, and subject to condition $x^2+y^2=1$:

So do I apply Lagrange's Multiplier method to find the maximum value?
I tried to find the numbers just by applying few numbers but it doesn't seem to work.

答: how about this inequality : $ x^2+y^2\geq 2xy$ it would simplify things.</p>


问:
Gradient step in a graph and average of a function
Suppose that you have a function $f$ on the nodes $V$ of a graph. For a node $x$, define de node $\phi_fx$ to be the neighbor of $x$ such that the $f(y)-f(x)$ has the highest positive value and $\phi_fx = x$ if $f(y)-f(x)<0$  for all $y$. So $\phi_f$ is following the gradient for one step. Let $d_x$ be the degree of the node $x$. Is it true that if $x$ is random uniform
$$
\mathbb{E}_x [d_{\phi_fx} f(\phi_fx)] \geq \mathbb{E}_x [d_{x}f(x)]
$$
Of course climbing the gradient increases $f$ but the degree term messes things up a bit.

答:
It is false in general. Take the graph $K_{1,3}=(\{v\}\cup \{u_1,u_2,u_3\}, E)$ and the function with values $f(v)=1$ and $f(u_i)=2$. And we have $d_v=3$ and $d_{u_i}=1$. Then
$$\sum_{x\in V}d_x f(x) = 9$$
$$\sum_{x\in V}d_{\phi_f x} f(\phi_f x)=8.$$


问:
Find $\lim_{(x,y)\to(0,0)} \frac{xy^3}{x+y}$
I have to compute $\displaystyle\lim_{(x,y)\to(0,0)} \frac{xy^3}{x+y}$.

When doing polar coordinates, I get $\displaystyle\lim_{r\to0}r^3\frac{\sin^3(\theta)}{\sin(\theta)+\cos(\theta)}$ but I'm not sure if I can say it's zero because of that denominator.

I also tried this limit through lines, a parabola, and axis, all of them zero.

My professor said something about "what happens whe  $x+y=0$?" And the hint was to take $\displaystyle\frac{xy^3}{x+y}=1$ which implies $\displaystyle x=\frac{y}{y^3-1}$ and we have to check what happens when $y\to0$. However, that leads to $0$. I don't understand what is happening in $\displaystyle x=\frac{y}{y^3-1}$, maybe something related to mean values theorem?

答:
Suppose $x = \varepsilon - y$ so that $x + y = \varepsilon$. Then

$$ \frac{xy^3}{x + y} = \frac{(\varepsilon - y) y^3}{\varepsilon} = y^3 - \frac{y^4}{\varepsilon}.$$

So no matter how small $y$ is, we can always choose $\varepsilon$ to make $\frac{y^4}{\varepsilon}$ very very large.

Just make sure that $(\varepsilon - y, y) \to 0$ when you're working out what to choose for $\varepsilon$.

But if you want to continue from $$x = \frac{y}{y^3 - 1},$$

then note that $y^3 - 1$ is an increasing function. So if say $|y| < 1/2$ then

$$\left( -\frac12 \right)^3 - 1 < y^3 - 1 < \left( \frac12 \right)^3 - 1.$$

So

$$ -\frac{8}{7} < \frac{1}{y^3 - 1} < -\frac{8}{9}, $$

and therefore $|x| < \frac{8}{7} |y|$.

Really, we're just using the fact that $y^3 - 1 \not\to 0$.


问:
Arrange letters of the word COMPUTE so that vowels OR consonants are in alphabetical order OR at least two vowels next to each other.
Question: How many ways are there to arrange the letters of the word COMPUTE so that vowels OR consonants are in alphabetical order OR at least two vowels next to each other.

I have tried lots of things to solve this question.
I have started by looking for the number of permutations where vowels are in alphabetical order. (7!/4!) Then, I looked for the number of permutations where all the consonants in alphabetical order. (7!/3!) Then I subtracted the number of arrangements where all the consonants and vowels are in alphabetical order. (C(7,3)). That is the point I stuck.
How should I include the condition of having "OR at least two vowels next to each other." ?

答:
Start by counting the number of ways to choose the positions of the vowels: $\binom{7}{3}=35$

Then find how many of these do not have vowels in consecutive positions. With four consonants, there are five places to insert vowels: _c_c_c_c_ Choose three of them: $\binom{5}{3}=10$

So there are $35-10=25$ patterns that meet the condition of having consecutive vowels. For each of these there are $4!$ permutations of the consonants and $3!$ permutations of the vowels. This gives a total of $25\times 4!\times 3!=3600$ permutations with at least two vowels next to each other.

For the $10$ patterns that do not have consecutive vowels, there are $4!$ permutations with the vowels in order and $3!$ with the consonants in order. The permutation with both groups in order is counted twice, so there are $4!+3!-1=29$ permutations with at least one group in alphabetical order. This gives a total of $10\times 29=290$ additional permutations that meet the given conditions.

The total is therefore $3890$ arrangements.


问:
Uniform distributed sequences
If $X_n$ uniformly distributed $U[0,X_{n-1}=x_{n-1}]$ for $n>0,  X_0=1$.
How do we show the sequence $X_n^a$ is uniform.

Title: Uniform distributed sequences

Body: $E(S_{n+1}|S_1,S_2,..,S_n)=(1+a)^{n+1} E(X_{n+1}^{a}| X_1,X_2,\dots,X_n)$ since $\sigma (S_1,S_2,\dots,S_n)=\sigma (X_1,X_2,\dots,X_n)$ Hence $E(S_{n+1}|S_1,S_2,\dots,S_n)=(1+a)^{n+1} \frac {\int_0^{X_n} t^{a}dt} {X_n}=(1+a)^{n} X^{a}_n=S_n$.


问:
Understanding weighted linear least square problem
I am having difficulty in understanding about weighted linear least squares.
Could anybody explain me instead of minimizing the residual sum of squares why we need to minimize the weighted sum of squares? Further, I want to know about the term weighted?
Although I have gone through some wiki notes but I am not able to understand.

Thank you very much for the help.

答:
Take a look at a simple problem:
$$ax=c\\
bx=d$$
where '$=$' is meant as an optimization goal, not as exact equality. So we want to find $x$ such that the error of both equalities is minimized in some optimal sense. If you choose a least squares criterion we get the following error function:

$$\epsilon = (ax-c)^2+(bx-d)^2$$

Now we can decide that for some reason the error in the first equation is more important than the error in the second equation, so we can add a weight ($>1$) to the error component of the first equation:

$$\hat{\epsilon} = w^2(ax-c)^2+(bx-d)^2$$

Minimizing $\hat{\epsilon}$ will result in a smaller error for the first equation at the expense of the error of the second equation. This is the basic idea of a weighted least squares error criterion.

If you solve the original (unweighted) problem by solving $\frac{d\epsilon}{dx}=0$ you get the optimal solution:

$$x_o=\frac{ac+bd}{a^2+b^2}$$

If you solve the weighted least squares problem by solving $\frac{d\hat{\epsilon}}{dx}=0$ you get

$$\hat{x}_o=\frac{w^2ac+bd}{w^2a^2+b^2}$$

From this you can see that if the weight $w$ is chosen very large, the solution $\hat{x}_o$ becomes close to $\frac{c}{a}$, which is simply the exact solution of the first equation, not at all considering the second equation. Obvioulsy, by using a weight $w>1$ you give more importance to the first equation.


问:
Degree of a covering map and induced homomorphism
Consider the equivalence relation on $\mathbb{S}^1$ given by identification of antipodal points  $x \sim y \iff x = \pm y$

I have shown that the quotient map $\pi : \mathbb{S}^1 \to \mathbb{R}P^1$ is a $2$-sheeted covering map for projective line, i.e $\pi^{-1}([y]_\sim) = \{y, -y\}$. In a textbook I am reading, the degree of a covering map is defined as the cardinality of a fiber. Here it's two.
But I have also read that we can consider the induced homomorphism $$\pi_{*} : \pi_1(\mathbb{S}^1, y) \to \pi_1(\mathbb{R}P^1, [y]) \quad \quad \gamma \mapsto \pi \circ \gamma$$ and since both groups here are $\mathbb{Z}$, we can think of $\pi_{*}$ as multiplication by some integer $n \in \mathbb{Z}$ : $k \mapsto n k$ and that's its degree.

I think both definitions are equivalent, right? How do I show using second definition that $n = 2$? (I know very little group theory)

答: You have a homeomorphism $\Bbb{R}P^1 \cong S^1$ given by $[z] \mapsto  z^2$, so the composition $S^1 \to \Bbb{R}P^1 \cong S^1$ is the map $z \mapsto z^2$. From there it's clear that $\pi_*(1) = 2$.


问:
Deduction rules involving set $\Gamma$ of premises versus elementary textbook natural deduction rules. How do they differ exactly?
In elementary textbooks, natural deduction rules are presented in the following way, say, for $\&$-Intro

from $\phi$ and $\psi$, infer $\phi\&\psi$

or

$(n).....\phi$

$(m)....\psi$

$\therefore$

$(p)....\phi\&\psi$.

I would like to know to what extent does the following way of stating $\&$-Intro differs from the above  " ordinary" textbook presentation. The way I'm referring to is the one I find in Shapiro's presentation of classical logic (https://plato.stanford.edu/entries/logic-classical/#Dedu):

(&I) If Γ1⊢θ and Γ2⊢ψ, then Γ1,Γ2⊢(θ&ψ).

( meaning : " if $\theta$ is derivable from a set of premises $\Gamma_1$ anf if $\psi$ is derivable from a set of premises $\Gamma_2$, then $(\theta\&\psi)$ is derivable from a set of premises $\Gamma_1\cup\Gamma_2$.")

Can Shapiro's presentation be termed " natural deduction"? Or rather is it a case of " sequent calculus"?

Aside : Do you know any beginner's textbook on mathematical logic that displays examples of derivations in Shapiro's style?

答:
The 'elementary textbook' rule is that: when $\phi$ and $\psi$ may be derived, then we may infer that $\phi\mathop\&\psi$ may be derived.   It is unstated that these derivations take place in the same context ( premises and assumptions ).   This rule of inference might be sumarised as $$\dfrac{~\phi\qquad\psi~}{\phi\mathop\&\psi}{\small\&\mathsf I}$$

The 'sequent calculus' rules extend this to explicitly list under which context things are derived.   The same rule above may be then presented with the context ($\Gamma$, a set of statements) explicitly stated: $$\dfrac{~\Gamma\vdash\phi\qquad\Gamma\vdash\psi~}{\Gamma\vdash\phi\mathop\&\psi}{\small\&\mathsf I}$$

We can then extend the rule so to say: when $\phi$ and $\psi$ may be derived in contexts $\Gamma_1$ and $\Gamma_2$ respectively, then we may infer that $\phi\&\psi$ may be derived in the united context, $\Gamma_1\cup\Gamma_2$.

$$\dfrac{~\Gamma_1\vdash\phi\qquad\Gamma_2\vdash\psi~}{\Gamma_1\cup\Gamma_2\vdash\phi\mathop\&\psi}{\small\&\mathsf I}$$

Long story short: the advanced presentation says the same thing as the elementary presentation, but with some additional details added.


问:
Cospectral graphs that are non-isomorphic and that only have simple eigenvalues
It is a well known fact that there are non-isomorphic connected graphs whose adjacency matrix have the same spectrum.

This has been discussed, for example, in this older post.

However, in the examples given, the graph spectrum always some has repeated eigenvalues. Are there examples where this is not the case, but rather each eigenvalue is unique?

On a different but related problem: Is it true that if two graphs have only single eigenvalues (multiplicity 1) in their spectrum, then it is easy to determine if they are isomorphic or not?

答:
Yes, it is easy to determine if they are isomorphic or not as long as they are cospectral and have distinct eigenvalues (multiplicity 1).

But you cannot directly say that they are isomorphic. As Misha gave an example which has same distinct eigenvalues but they are not isomorphic.

Let $A,B$ are adjacency or laplacian of two graphs that you want to test. Their eigendecompositions are $A=U \Sigma U^{T}$ and  $B=V \Sigma V^{T}$. See their eigenvalues ($\Sigma$ is a diagonal matrix which keeps eigenvalues) are the same and let's suppose it has distinct values.
$S$ is a diagonal matrix that includes $\mp1$ and $P$ is a permutation matrix where each column and row there is single 1 and rest of them 0.

If you find $P$ and $S$ matrices that meets $PU=VS$ then they are isomorphic, unless they are not.

If some eigenvalues are repeated in $\Sigma$, even though you find $P$ and $S$ matrix that meets $PU=VS$, still you cannot say they are isomorphic.


问:
Understanding a theorem about Dedekind domains.
I am reading "A Course in Ring Theory" by Passman.

I was reading Theorem $7.8$ which state

"Let $R$ be a Dedekind domain with field of fractions $F$ and let $K$ be a finite degree separable field extension of $F$. If $S$ is the set of elements of $K$ that are integral over $R$, then $S$ is a Dedekind domain."

The proof then starts of with:

"To start we know that $S$ is a subring of $K$, having $K$ as its field of fractions. Indeed, if $\alpha \in K$, then there exists $0 \neq r \in R$ with $r\alpha \in S$. Furthermore, $S \cap F = R$, since $R$ is integrally closed.  It remains to verify conditions $(1), (2),$ and $(3)$ of the definition of a Dedekind domain.

$(1)$ In view of the preceding remarks, we can let $\{\alpha_1, \alpha_2, \cdots, \alpha_n \}$ be an $F-$basis for $K$ with each $\alpha_i \in S$. Notice that multiplication by any $\beta \in K$ determines an $F$-linear transformation of the $F-$vector space $K$. We can therefore let tr$\beta$ denote the trace of this linear transformation. In other words, if $\beta \alpha_i = \sum_{j = 1}^n f_{i,j}\alpha_j$ with $f_{i,j} \in F$, then tr$\beta = \sum_{i = 1}^n f_{i,j}$. Clearly, tr$: K \rightarrow F$ is an $F$-linear functional and it is not hard to see that if $\beta \in S$, then tr$\beta \in S \cap F = R$. Furthermore, since $F/K$ is separable, we know that the $n \times n$ matrix (tr$\alpha_i \alpha_j$) is non singular. "

*** My problems: I don't really follow, why if $\beta \in S$ then tr$\beta \in S$, or why the $n \times n$ matrix (tr$\alpha_i \alpha_j$) is non singular.

For if $\beta \in S$ then tr$\beta \in S$, I know since $S$ is a ring and $\alpha_i \in S$ we have $\beta\alpha_i \in S$. Also since $S$ is a ring, if each $f_{i,i} \in S$ then tr$\beta \in S$, so I have been trying to prove each $f_{i,i} \in S$, but have not had any luck.

Sadly I haven't made any progress at all on why he $n \times n$ matrix (tr$\alpha_i \alpha_j$) is non singular.

答:
Non-degeneracy of a bilinear map $\beta:V\times W\to k$ for $k$ vectorspaces $V,W$ means that, for $0\not=v\in V$, there is $w\in W$ such that $\beta(v,w)\not=0$, and symmetrically.

The fact you are wanting to prove is apparently the (well-known) non-degeneracy of the trace pairing $\beta(x,y)=\hbox{tr}^K_k(xy)$ from a finite, separable field extension $K$ of a field $k$.

To write things in terms of matrices and so on is not helpful, I think.

Rather, existence of a primitive element, a zero of a polynomial with no repeated roots (so the derivative of the polynomial does not vanish at that element) is what you need.

This is quite standard, and eminently google-able. It is certainly in my own algebra notes, among nearly-infinitely-many other on-line sources.

I understand that "non-degeneracy of a pairing" might be unfamiliar, but it is the correct notion here. For example, "positive-definiteness", a cousin of this notion, is not quite applicable.


问:
Factoring $4x^{4} - x^{2}$ into $4x^{2}(x-1/2)(x+1/2)$
So i was trying to make an integral but i'm stuck with the easiest part.

How do you get this?
$$4x^{4} - x^{2} = 4x^{2}(x-1/2)(x+1/2)$$

I know how to take the roots $x = 0$, $x = \pm 1/2$,
but when putting it all together I get
$$x(x−1/2)(x+1/2)$$ and I can't remember how to do it correctly.

答:
I think you meant $4x^{4} - x^{2}$. In such case, you can factor $x^{2}$ out and apply the following identity:

\begin{align*}
a^{2} - b^{2} = (a+b)(a-b)
\end{align*}

At your case, you have $4x^{4} - x^{2} = x^{2}(4x^{2} - 1)$, where $a = 2x$ and $b = 1$. Consequently, we get that
\begin{align*}
4x^{4} - x^{2} = x^{2}(2x-1)(2x+1) = 4x^{2}(x-1/2)(x+1/2)
\end{align*}


问:
Optimization Question Finding closest point
Find the point on the graph of the function that is closest to the given point.

The function: $f(x)= \sqrt {x-8}$; the point: $(15,0)$

答:
Given two points

$$
\cases{p_0=(15,0)\\
p=(x,\sqrt{x-8})}
$$

the squared distance is given by

$$
\|p-p_0\|^2= d^2
$$

or

$$
(x-15)^2+(\sqrt{x-8}-0)^2 = x^2-30x+15^2+x-8 = d^2
$$

but

$$
x^2-30x+15^2+x-8 = \left(x-\frac{29}{2}\right)^2+\frac{27}{4}=d^2
$$

so we can conclude that $d^2$ is minimum for $x=\frac{29}{2}$ and the minimal distance is $d=\frac{3\sqrt{3}}{2}$


问:
Prove set of branch points is discrete assuming...
Let $X$ and $Y$ be connected Riemann surfaces. Let $F: X \to Y$ be holomorphic non-constant (and thus open and continuous). Denote the set of ramification points $Ram(F) :=\{p \in X  \ | \ mult_pF \ge 2\}$ and the set of branch points $Branch(F) := F(Ram(F))$.

Question 1: Just to double check, are the following correct?

$Ram(F)$ is discrete, and I think $Ram(F)$ is also closed for the same reason $Ram(F)$ is discrete.

Apparently, for any discrete subspace $A$ of $X$, $F(A)$ is not necessarily discrete.

$F$ is 'discrete' in the sense that its fibres are discrete (i.e. each $F^{-1}(y)$ is discrete, for any $y \in image(F)$, or even $y \in Y$) but not necessarily in the sense that $F$ maps discrete sets to discrete sets.

For $X$ compact, we have that $F$'s image is compact, and $F$ is surjective. Thus, $Y$ is compact.

For $X$ compact, $F$ is a proper and closed map because $Y$ is Hausdorff and because $F$ is continuous.

Question 2: For $X$ compact, is $Branch(F)$ discrete? (possibly answered Question 3)

Question 3: More generally, for $X$ compact and for any closed discrete subspace of $A$ of $X$, is $F(A)$ discrete?

Question 3.1: I think yes: closed discrete subspace of compact is finite $\implies$ $A$ is finite $\implies$ $F(A)$ is finite $\implies$ $F(A)$ is discrete because finite subspaces of Fréchet/T1 are discrete. Is this correct?

Question 3.2: In general for any map $F: X \to Y$ of any topological spaces $X$ and $Y$ with $X$ compact and $Y$ Fréchet/T1 and for any closed discrete subspace $A$ of $X$, we have $F(A)$ discrete. Is this correct?

In particular, I think this means we do not use that $F$ is proper, closed, open, surjective, non-constant or holomorphic or that $X$ is connected or that $Y$ is connected. We can relax this to $X$ compact (and not necessarily Riemann surface) and $Y$ Fréchet/T1 (and not necessarily Riemann surface, Hausdorff/T2 or compact).

Question 4: (I was about to ask alternatives to that $X$ is compact to say $F(Ram(F))$ or even $F(A)$ is discrete, but I think this is another story already.)

Related:

Set of branch points isn't discrete, but branch points are isolated?

About branch points of a holomorphic map

Are branch points always isolated?

When closed and continuous maps discrete to discrete

答: I believe yes to questions 1,2,3,3.1 and 3.2.</p>


问:
On the Shrinking Lemma (M. Spivak's Comprehensive Intro to Diff. Geom.)
I am familiar with the following notion of a shrinking or contraction lemma

Theorem: Given a complete metric space $(M,d)$ and a map $f$ into itself. If there exists a constant $K\in (0,1)$ such that $$d(f(x),f(y))\leq K d(x,y) $$ for any two $x,y\in M$, then $f$ has a unique fixed point $p\in M$. Moreover, the sequence of iterations of $f$ on any point $x_0\in M$ converges to $p$ (that is $\{(\underbrace{f\circ...\circ f}_{n\text{ times }})(x_0) \}_{n\in \mathbb{N}}\to p$).

Now, in A Comprehensive Introduction to Differential Geometry by M. Spivak, Theorem 13 states the following

Theorem (The Shrinking Lemma): Let $\mathcal{O}$ be an open locally finite cover of a manifold $\mathcal{M}$. Then it is possible to choose, for each $U$ in $\mathcal{O}$, an open set $U'$ with $U'\subset U$ in such a way that the collection of all $U'$ is also an open cover of $\mathcal{M}$.

Firstly, the proof is fairly easy to follow but an assumption is made, which I do not really get. Spivak claims that we can obviously assume that $\mathcal{M}$ is connected, which I think follows from that fact that any manifold is the disjoint union of countably many connected manifolds, but still is not that clear to me. Secondly (and I think this might be more interesting) what is exactly the relation of these two theorems which apparently hold the same name.

Thanks in advance

答:
Your version of the shrinking lemma may have a typo. As currently written, we can take $U' = U$. I think you mean we require $\overline{U'} \subset U$, where $\overline{U'}$ denotes the closure of $U'$. An open subset of a disjoint union is simply the disjoint union of open subsets of the base spaces. For example, $U\sqcup V \subset M\sqcup N$ is open if and only if $U, V$ are both open, this holds for a disjoint union over any indexing set. Thus once the theorem is proved in the connected case, the general case just follows by applying the theorem to each connected component, which is how the reduction was made.

The first theorem is the Banach fixed point theorem. It says that a contraction mapping in a complete metric space has a unique fixed point. It is used in various places in mathematics to prove the unique existence of something. For instance in Differential equations and Differential topology. The shrinking lemma on the other hand is used to prove that every open cover of a manifold has a partition of unity. It is much less ubiquitous within mathematics, I would say. The fact that they have similar names is a matter of chance (I would also say), in that they are fundamentally different.


问:
Implicit equation for the image of immersion $(\cosh(t),\sinh(t))$
how can I discribe a implicit equation for the Image of
$$
f(t)=(\cosh(t),\sinh(t)),
$$
knowing that this is an injective immersion? This doesn't look that hard, but I can't proceed.

Thanks in advance!

答: Observe that $x^2-y^2=1$ so your image is contained in the hyperbola. Also, since $\cosh t>0$ your image is the right branch of the above equilateral hyperbola.


问:
Approximation of matrix in 2-norm

Given a rank-$k$ matrix $A$, find a rank-$j$ matrix $B$, where $j<k$, such that $\|A-B\|_2$ is minimal.

My idea was to choose, if

$$A=P \operatorname{diag}(\sigma_1,\ldots,\sigma_k,0,\ldots) Q^H$$

then

$$B=P \operatorname{diag}(\sigma_1,\ldots,\sigma_j,0,\ldots) Q^H$$

Is this approach correct? If so, then I would try to prove that this is actually the best approximation.

答: The approach is correct if you ensure that the eigen values are ordered in such a way that $\sigma_{j+1},\ldots,\sigma_k$ are the smallest possible (in absolute value)</p>

Title: Approximation of matrix in 2-norm


问:
Fourier transform of a tempered distribution : why a link with classical Fourier transform?
Fourier transform ($F$) of tempered distribution $\operatorname{sinc}$ is tempered distribution $\operatorname{Rect}$.

Does it mean that tempered distributions $F(\operatorname{sinc})$  and $\operatorname{Rect}$ behave the same as far as integration against Schwartz functions goes?

If so, how the latter (intuitively) proves that the Fourier transform (not in the sense of distributions) of $\operatorname{sinc}$ is indeed $\operatorname{Rect}$?

In other words : how does this prove that Fourier transform of $\operatorname{sinc}$ in the sense of distribution is Fourier transform of $\operatorname{sinc}$ in the sense of functions?

答:
Do you mean the Fourier transform of $sinc$ in $L^2$ sense or in pointwise sense ie. the improper Riemann integrals $\int_{-\infty}^\infty sinc(x)e^{-2i\pi \xi x}dx$ ?

The Fourier transform of $sinc$ in the sense of distributions (call it $T$) tells us $\lim_{n\to \infty}\int_{-\infty}^\infty sinc(x) e^{-2i\pi \xi x} e^{-\pi x^2/n^2}dx \tag{1}$

not the same as the improper Riemann integral (well it is the same for $|\xi|\ne 1/2$ but it needs a proof specific to $sinc$)

$(1)$ gives the Fourier transform of $sinc$ in $L^2$ sense as $\lim_{n\to \infty} T \ast ne^{-\pi n^2 x^2}$, limit in $L^2$ sense, since $T$ is the distribution $rect$ then it is $\lim_{n\to \infty} rect \ast ne^{-\pi n^2 x^2}=rect$, limit in $L^2$ sense.


问:
How Do Heyting Algebras Relate To Logic?
My question is, broadly speaking, how are Heyting algebras related to logic ? It would be great if someone could answer this question without being too technical (or point to easy to read literature). I know about category theory, but not much about logic. I know Heyting algebras correspond with the lattices of subobjects in toposes, and I've heard Heyting algebras somehow model intuitionistic logic, but I would really appreciate knowing more about it. I hope my question is not too vague.</p>

答:
As Noah Schweber says, this is a generalization of how Boolean algebras relate to logic, so it would be good to get a handle on that case first. A Boolean algebra $B$ is a set equipped with two elements $\bot, \top$ and operations $\wedge, \vee, \neg$ satisfying the axioms of propositional logic; the intended interpretation is that $B$ is a collection of propositions, $\bot$ is "false," $\top$ is "true," $\wedge$ is "and," $\vee$ is "or," and $\neg$ is "not."

In every Boolean algebra the law of excluded middle $b \vee (\neg b) = 1$ is satisfied. Heyting algebras are, most concretely, a generalization of Boolean algebras in which the law of excluded middle is dropped, and hence which model (propositional) intuitionistic logic.

The definition of a Heyting algebra can be stated and motivated categorically, as done e.g. in my blog post How to invent intuitionistic logic, which explains everything I'm about to explain in more detail. We start by taking the point of view that the most fundamental concept when it comes to propositions is implication, and axiomatize implication as defining a partial order $p \le q$ on the set of propositions (in particular, transitivity corresponds to biconditional introduction: the rule of inference that $p \le q$ and $q \le r$ implies $p \le r$).

Remarkably, every other logical operation now corresponds to requiring that certain universal operations exist with respect to this partial order (in particular, in this framework their properties such as commutativity and associativity are theorems, not axioms):

$\bot$ is the initial object: this says that $\bot$ is characterized by the property that $\bot \le p$ (false implies everything),

$\top$ is the terminal object: this says that $\top$ is characterized by the property that $p \le \top$ (everything implies true),

$p \wedge q$ is the product / meet: this says that $p \wedge q$ is characterized by being universal wrt the property that $p \wedge q \le p$ and $p \wedge q \le q$,

$p \vee q$ is the coproduct / join: this says that $p \vee q$ is characterized by being universal wrt the property that $p \le (p \vee q)$ and $q \le (p \vee q)$,

$\neg p$ is the pseudocomplement: this says that $\neg p$ is characterized by being universal wrt the property that $p \wedge (\neg p) = \bot$ (the principle of explosion).

In particular, every Boolean algebra is partially ordered by implication: explicitly, $p \le q$ iff $\neg p \vee q = \top$ (either $p$ is false or $q$ is true), and you can check that all of the above operations exist and have the stated universal properties in a Boolean algebra. So the implication partial order recovers all of the other operations, along with all of their properties.

We can generalize $\neg$ by asking that there exists an object $p \Rightarrow q$ which is universal with respect to the property that $p \wedge (p \Rightarrow q) \le q$; this is (internal) implication, or "relative pseudocomplement," and it recovers negation via taking $\neg p = (p \Rightarrow \bot)$. It can be described in a nice categorical way as follows: asking that $\bot, \top, \wedge, \vee$ exist means asking that propositions form a poset which has all finite limits (/ products / meets) and colimits (/coproducts / joins); these are the (bounded) lattices. To get a Heyting algebra we ask in addition that all implications $p \Rightarrow q$ exist, which is equivalent to asking for all exponential objects. This means that, categorically:

A Heyting algebra is a bicartesian closed poset.

In any Heyting algebra we always have $p \le \neg \neg p$, and we generally do not have equality; if we do, the Heyting algebra must be a Boolean algebra. You can write down lots of interesting examples of Heyting algebras which are not Boolean algebras using the open subsets of most topologies. For more on this you can check out, for example, Vickers' Topology via Logic.


问:
Integral of Hermite polynomial multiplied by $\exp(-x^2/2)$
What is the value of $\int_{-\infty}^{\infty}e^{-\frac{x^2}{2}}H_n(x)dx$ where $H_n(x)$ is the $n^{\small\mbox{th}}$ Hermite Polynomial (physicist's convention)?</p>

答:
Using the generating funtion $e^{2xt-t^2}=\sum_{n=0}^\infty H_n(x)\frac{t^n}{n!}$ we can obtain two recurrence relations.

Differentiating with respect to $t$ we obtain $H_{n+1}(x)=2xH_n(x)-2nH_{n-1}(x)$ for $n\geq 1$ with $H_0(x)=1$ and $H_1(x)=2x$. Similarly, differentiating with respect to $x$ we obtain $\frac{d}{dx}H_n(x)=2nH_{n-1}(x)$ for $n\geq 1$.

Now, define $I_n=\int_{-\infty}^{\infty}e^{-x^2/2}H_n(x)dx$ then
$$\begin{align}I_{n+1}&=\color{blue}{\int_{-\infty}^{\infty}2xe^{-x^2/2}H_{n}(x)dx}-2nI_{n-1}\\
&=\color{blue}{-2e^{-x^2/2}H_n(x)\Big|_{-\infty}^{\infty}+4nI_{n-1}}-2nI_{n-1}=2nI_{n-1}.
\end{align}$$
where the integral in blue was solved by parts and since that $H_n$ is a polynomial of degree $n$ we have that $\lim_{x\to\pm\infty}e^{-x^2/2}H_n(x)=0$, therefore
$-2e^{-x^2/2}H_n(x)\Big|_{-\infty}^{\infty}=0$.

To finish, since $$I_0=\int_{-\infty}^{\infty}e^{-x^2/2}H_0(x)dx=\int_{-\infty}^{\infty}e^{-x^2/2}dx=\sqrt{2\pi}$$ and $$I_1=\int_{-\infty}^{\infty}e^{-x^2/2}H_1(x)dx=\int_{-\infty}^{\infty}2xe^{-x^2/2}dx=0$$ we conclude that $I_{2n+1}=0$ for all $n\in\mathbb{N}$ and
$$\begin{align}I_{2n}&=2(2n-1)I_{2n-2}\\
&=2^2(2n-1)(2n-3)I_{2n-4}\\
&~~\vdots\\
&=2^n(2n-1)(2n-3)\cdots1\cdot I_0\\
&=2^n\frac{2n(2n-1)(2n-2)(2n-3)\cdots1}{2n(2n-2)\cdots2}I_0\\
&=2^n\frac{(2n)!}{2^nn!}I_0\\
&=\frac{(2n)!}{n!}I_0\\
&=\frac{(2n)!}{n!}\sqrt{2\pi}.\end{align}$$


问:
What is the joint distribution of $(X,Y)$ under the $\mathbb Q$ equivalent probability measure?

Let $X$ and $Y$ be two independent standard random variables. Let $\theta$ be a
constant with $\theta^2 \in (0, 1)$ and define the $\mathbb P$-equivalent probability measure, $\mathbb Q$, by
$\frac{d\mathbb Q}{d\mathbb P}=\frac{e^{\theta XY}}{\mathbb E[e^{\theta XY}]}>0$. What is the joint distribution of $(X,Y)$ under $\mathbb Q$? Are $(X,Y)$ also independent under $\mathbb Q$?

My try:

Compute that
\begin{align}
\mathbb P(X<x_0, Y<y_0)&=\frac {1}{\mathbb E(e^{\theta XY})}\int_{-\infty}^{x_0}dx\int_{-\infty}^{y_0} e^{\theta xy}\frac 1{2\pi}e^{-\frac{x^2+y^2}{2}}dx\\
&=\frac{1}{2\pi\mathbb E(e^{\theta XY})}\int_{-\infty}^{x_0}e^{-x^2/2}dx\int_{-\infty}^{y_0}e^{-\frac 12(y-\theta x)^2-\frac 12\theta^2 x^2}dy
\end{align}
Let $t=y-\theta x$, then
$$ \mathbb P(X<x_0, Y<y_0)=\frac{1}{\sqrt{2\pi}\mathbb E(e^{\theta XY})}\int_{-\infty}^{x_0}e^{-\frac 12x^2-\frac 12\theta^2 x^2}dx\int_{-\infty}^{y_0-\theta x}\frac{1}{\sqrt{2\pi}}e^{-\frac 12 t^2}dy. $$

But I have not idea how to proceed. Also, the hint says maybe we can consider the moment generating function but we have the same type of issue that we cannot seperate $e^{\theta xy}$ and use the independence of $X$ and $Y$ under $\mathbb P$.

Body:
We know that $$d\mathbb{P}(x,y) = f_{X,Y}(x,y)\, dx\, dy = \frac{1}{2\pi} e^{-\frac{1}{2}(x^{2}+y^{2})}\, dx\, dy.$$

We can also show that $$d\mathbb{Q}(x,y) = \frac{d\mathbb{Q}}{d\mathbb{P}}\, d\mathbb{P}(x,y) = \frac{1}{2\pi\mathbb{E}[e^{\theta xy}]} e^{\theta xy - \frac{1}{2}(x^{2}+y^{2})}\, dx\, dy.$$

Now we calculate $\mathbb{E}[e^{\theta xy}]$:

\begin{align*}
\mathbb{E}[e^{\theta xy}] &= \frac{1}{2\pi} \int_{\mathbb{R}^{2}} e^{-\frac{1}{2}(x-\theta y)^{2} - \frac{1}{2}(1-\theta^{2})y^{2}}\, dx\, dy  \\
&= \frac{1}{\sqrt{2\pi}} \int_{\mathbb{R}} e^{-\frac{1}{2}(1-\theta^{2})y^{2}}\, dy \\
&= \frac{1}{\sqrt{1-\theta^{2}}} \cdot \frac{1}{\sqrt{2\pi}} \int_{\mathbb{R}} e^{-z^2/2}\, dz \\
&= \frac{1}{\sqrt{1-\theta^{2}}}.
\end{align*}

Now deduce that
$$d\mathbb{Q}(x,y) = \frac{\sqrt{1-\theta^{2}}}{2\pi} e^{\theta xy - \frac{1}{2}(x^{2}+y^{2})}\, dx\, dy.$$


问:
What is the name of Fibonacci variation when $F(n) = a\cdot F(n-1) + b\cdot F(n-2) + c$, were $c$ is a constant, and $a >0, \ b >0, \ c>0$
I am trying to write $\log(n)$ algorithm for the above. I don't know if there is a specific name for the Fibonacci variation when:

$$F(n) = a\cdot F(n-1) + b\cdot F(n-2) + c$$

where: $a >0, \ b >0, \ c>0$

Could someone help me with the name of this variation?

答:
Understanding that the function is null for negative $n$
$$
F(n) = aF(n - 1) + bF(n - 2) + c\quad \left| {\;F(n < 0) = 0} \right.
$$
so that its first values are
$$
\left\{ \matrix{
  F(0) = c \hfill \cr
  F(1) = \left( {a + 1} \right)c \hfill \cr
  F(2) = \left( {a\left( {a + 1} \right) + b + 1} \right)c \hfill \cr
  F(3) = \left( {a\left( {a\left( {a + 1} \right) + b + 1} \right)
 + b\left( {a + 1} \right) + 1} \right)c \hfill \cr
  \quad \quad  \vdots  \hfill \cr}  \right.
$$
then its o.g.f. will be derived as
$$
\eqalign{
  & G(z) = \sum\limits_{0\, \le \,n} {F(n)z^{\,n} }  =   \cr
  &  = a\sum\limits_{0\, \le \,n} {F(n - 1)z^{\,n} }  + b\sum\limits_{0\, \le \,n} {F(n - 2)z^{\,n} }
  + c\sum\limits_{0\, \le \,n} {z^{\,n} }  =   \cr
  &  = az\sum\limits_{1\, \le \,n} {F(n - 1)z^{\,n - 1} }
  + bz^{\,2} \sum\limits_{2\, \le \,n} {F(n - 2)z^{\,n - 2} }
  + c{1 \over {1 - z}} \cr}
$$
which gives
$$
\eqalign{
  & G(z) = {c \over {\left( {1 - z} \right)\left( {1 - az - bz^{\,2} } \right)}}
 = {{c/b} \over {\left( {z - 1} \right)\left( {z^{\,2}  + {a \over b}z - {1 \over b}} \right)}} =   \cr
  &  = {{c/b} \over {\left( {z - 1} \right)
\left( {z - \left( { - {a \over {2b}} + \sqrt {a^{\,2}  + 4b} } \right)} \right)
\left( {z - \left( { - {a \over {2b}} - \sqrt {a^{\,2}  + 4b} } \right)} \right)}} =   \cr
  &  = {{c/b} \over {\left( {z - 1} \right)\left( {z - r} \right)\left( {z - s} \right)}} =   \cr
  &  = {c \over b}\left( {{1 \over {\left( {s - 1} \right)\left( {s - r} \right)\left( {z - s} \right)}}
 + {1 \over {\left( {r - s} \right)\left( {r - 1} \right)\left( {z - r} \right)}}
 + {1 \over {\left( {r - 1} \right)\left( {s - 1} \right)\left( {z - 1} \right)}}} \right) =   \cr
  &  =  - {c \over b}
\left( {{1 \over {s\left( {s - 1} \right)\left( {s - r} \right)\left( {1 - {z \over s}} \right)}}
 + {1 \over {r\left( {r - s} \right)\left( {r - 1} \right)\left( {1 - {z \over r}} \right)}}
 + {1 \over {\left( {r - 1} \right)\left( {s - 1} \right)\left( {1 - z} \right)}}} \right) \cr}
$$

Therefore $F(n)$ will be
$$
F(n) = {A \over {s^{\,n} }} + {B \over {r^{\,n} }}
 +C
$$
which is valid for $r$ and $s$ even complex, provided that they are not such as to
make null one of the denominators above.


问:
P-NP related problems
This is a question on a practice final.

Which of the following statements are true? If it is false, what is the underlying reason behind that?

I. If 3-CNF-SAT is in P, then Clique is also in P.

II. For decision problems $L_{1}, L_{2}$ in NP, if P is not NP, $L_{1}$ is at least as hard as $L_{2}$, and $L_{2}$ is at least as hard as $L_{1}$, then $L_{1}$ and $L_{2}$ are NP-complete.

III. For decision problems $L_{1}, L_{2}$ in NP-complete, if $L_{1}$ is not in P, then $L_{2}$ is also not in P

We are told that only the third statement is True, but there's no explanation why on the key. I have tried to figure this out, and the only conclusion I've come to is:

(I) cannot be true because if A is polynomially reducible to B, this implies B is at least as hard as A, not vice-versa (Not sure if this is a correct conclusion, so feedback on this would be appreciated.)

This is the first time I'm learning about the notion of hardness, so I don't understand most of the technical explanations I've found. Any clarifications on why I, II is incorrect, and why III is correct would be appreciated.

Self study I've done includes reading multiple StackExchange posts, multiple Wiki pages, and the corresponding section in the Cormen book. I just personally understand concepts better if I see different explanations.

答:
1 is true. 3-cnf-sat and clique are both NP-complete. This means that they are reducible to each other. Therefore, if 3-cnf-sat is in P, then P = NP and clique is also in P.

2 is false. The two problems might not be NP-hard. For example, both problems are in P and reduce to each other.

3 is true. If the two problems are NP complete, then they reduce to each other, so one of them is in P iff the other one is.

Title: P-NP related problems


问:
Directional derivative of Cartesian coordinate functions
I'm going through the book "A Visual Introduction to Differential Forms and Calculus on Manifolds by Jon Pierre Fortney" and on page 61 of the book there is the following exercise:

Explain that the rate of change of the Cartesian coordinate function $x$ in the $x$-direction is indeed one, thereby showing that $\frac{\partial x}{\partial x} = 1$. It may be helpful to consider how $x(p)$ changes as the point $p$ moves in the $x$-direction.

I'm struggling to understand what the exercise actually wants me to do.

答:
The directional derivative of $f$ at $p$ in direction $\mathbf{u}$  is
$$D_\mathbf{u}f(p) = \lim_{t\to 0}\frac{f(p+t\mathbf{u})-f(p)}{t}$$
Envision $p+t\mathbf{u}$ as a path passing through $p$ at unit speed in a direction parallel to the unit vector $\mathbf{u}$.

A partial derivative is a directional derivative in the positive direction of one of the coordinate axes, so in this case $\mathbf{u}=(1,0,0)$. For $p=(a,b,c)$,
$$\frac{df}{dx}(p) = D_\mathbf{u}f(p) = \lim_{t\to 0}\frac{f(p+t\mathbf{u})-f(p)}{t} = \lim_{t\to 0}\frac{f(a+t,b,c)-f(a,b,c)}{t}.$$
If now we take $f$ to be the $x$-coordinate function, then $f(a,b,c)=a$, and
$$\frac{df}{dx}(p) = \lim_{t\to 0}\frac{a+t-a}{t}.$$
Now replace $f$ with $x$, to match the given notation for the $x$-coordinate function.


问:
Passing Weak Convergence Through a Function?
Let $f_k,f : \mathbb{R}^d\to \mathbb{R}$. Assume $f_{k}$ converges weakly to $f$ in $L^p(\mathbb{R}^d)$. Let $p:\mathbb{R}\to \mathbb{R}$ be some function.

What can say about the weak convergence of $p(f_k)$ (what are some general assumptions on $p$ that one would expect to need)? The reason I ask is I have two terms in an equation in which I want to evaluate as $k\to\infty$, these are

$$ \int_{\mathbb{R}^d} \varphi_1(x)f_k(x)+ \varphi_2(x)p(f_k(x))~dx  $$

where $\varphi_i\in C^\infty_c(\mathbb{R})$, infinitely differentiable compact support, i.e are test functions. I don't mind if I can evaluate this limit $k\to\infty$ up to a subsequence.

答:
It seemed a good idea to me to assume $p$ as Lipschitz continuous for some nice resutlts, however in the comments I was shown that it doesn't really get you anywhere by itself, so I have edited the answer cancelling the wrong fact I had wrote, but still what follow works.

Also with the "famous" theorem (1.1 in here):

Theorem 1.1. $(1 < p < +\infty)$ Let $\{f_n\}$ be a bounded sequence in $\textit{L}^p(U)$. Then there exists a subsequence $\{f_{n_k}\}$ which converges weakly to some $f\in \textit{L}^p(U)$.

With this result you could also argue that, for weak convergence of at least a subsequence of $\{ p(f_k) \}$, you only need the boundedness of $||p(f_k)||_p$.