问:
What is a polynomial with integer coefficients called?
What is the proper mathematical name for a polynomial with only integer coefficients?

Having done some searching myself, I found "numerical polynomial" but these have integer values for integer parameters, and don't necessarily have to have integer coefficients.

As a related question, is there a name for polynomials with only rational coefficients?

答:
It is common to use the phrase integer polynomial to mean a polynomial with integer coefficients, consistent with describing a polynomial with real coefficients as a real polynomial or a polynomial with complex coefficients as a complex polynomial.

Any ambiguity arises from the dual nature of polynomials as formal expressions and as functions.  As your Question notes, there can be rational polynomials which take only integer values at integer arguments, so the best practice is to introduce (define) your meaning for integer polynomials along with notation, e.g. an integer polynomial is an element of $\mathbb Z[x]$ as @J.W.Tanner suggests (in the univariate case).

Likewise we can write $\mathbb Q[x]$ to clarify the meaning of "rational polynomials" as polynomials with rational coefficients.  It is always permitted to an author to redefine terminology (and notation) to suit the immediate needs of exposition, but incumbent on them to provide a clear definition and point out the (potential) deviation from convention.


问:
How to prove that $\frac{\pi}{2}=\left[1, 1, \tfrac{1}{2},\tfrac{1}{3},\tfrac{1}{4},\ldots\right]$?
I don't know how to prove the generalized continued fraction
$\pi/2=[1;1/1,1/2,1/3,1/4,...]=1+\cfrac{1}{1/1+\cfrac{1}{1/2+\cfrac{1}{1/3+\cfrac{1}{1/4+\ddots}}}}$

It appears on wikipedia without proof, it contains the terms of the harmonic series but it seems not to be very well known.

I would appreciate any help, thanks.

答:
The article shows that as the harmonic series $\sum\frac{1}{n}$ diverges, one can apply Van Vleck's theorem to show that the $2n$th and $(2n+1)$th convergents of the continued fraction $[1; 1, 1/2, 1/3,\dots]$ both exist and converge to the same limit.

The author transforms $[1;1,1/2,1/3,\dots]$ into the form
$$1+\frac{1\cdot1}{1+\frac{1\cdot2}{1+\frac{2\cdot3}{1+\dots}}}$$
by multiplying the numberator and the denominator of the $n$th fraction by $n$. Let $f_n$ be the numerator or the denominator of the $n$th (even) convergent then $f_n$ satisfies the relation
$$f_n=(2n^2-4n+3)f_{n-2}-(n-1)(n-2)^2(n-3)f_{n-4}$$
By direct substitutions, one can show that $A_n$ and $B_n$ where $A_n=\prod_{k\text{ even}}^nk^2$ and $B_n=(n+1)\prod_{k\text{ odd}}^{n-1}k^2$ satisfy the relation for even $n$s. The fraction $\frac{A_n}{B_n}$ has a limit known as the Wallis product. Since for odd $n$s the $n$th convergent converges to the same limit as previously proved, the continued fraction converges to $\frac{\pi}{2}$.

I hope this is a clear summary of the article that can save you some time. Sorry for falsely flagging your question.

Edit:

(1) If you are not familiar with the Van Vleck theorem, it is helpful to study the Seidel-Stern theorem. This theorem states that if $\sum b_n=\infty$ and $b_n$ positive, then $K(1/b_n)$ (the continued fraction) converges. The proof of this theorem can be found in Waadeland and Lorentzen's text Continued Fractions with Applications, Chapter 3 Theorem 3. The proof takes advantage of the fact that
$$\frac{A_{2n+1}}{B_{2n+1}}-\frac{A_{2n}}{B_{2n}}=\frac{1}{B_{2n}B_{2n+1}}\to 0$$
as $n\to\infty$. This can be seen from the recursive relation
$$B_{n}=b_nB_{n-1}+B_{n-2}$$
Since the $b_n$ are positive, we have $B_{2n}>B_{2n-2}>\cdots>B_0=1$ and $B_{2n+1}>\cdots>B_1=b_1$. Therefore
$$B_{2n}>b_{2n}b_1+B_{2n-1}>\cdots>(b_{2n}+b_{2n-2}+\cdots+b_2)b_1+1$$
and
$$B_{2n+1}>b_{2n+1}+B_{2n-1}>\cdots>b_{2n+1}+b_{2n-1}+\cdots+b_1$$
Since $\sum b_n$ divergese, the denominator goes to infinity with $n$.

Van Vleck's theorem, on the other hand, concerns the convergence of the continued fraction $K(a_n/b_n)$ with complex $a_n, b_n$. It gives a more general criterion for convergence according to the argument of $b_n$ and the divergence of $\sum |b_n|$ (in our case the argument is zero and $|b_n|=b_n$).

(2) The recursive relation is in no way magical. Let $f_n$ be the denominator or the numerator of the $n$th convergent, we have
$$f_n=b_nf_{n-1}+a_nf_{n-2}$$
$$f_{n-1}=b_{n-1}f_{n-2}+a_{n-1}f_{n-3}$$
$$f_{n-2}=b_{n-2}f_{n-3}+a_{n-2}f_{n-4}$$
like any continued fraction. Then $f_{n-3}=1/b_{n-2}(f_{n-2}-a_{n-2}f_{n-4})$. Plugging the second relation into the first one, one gets
$$f_n=(b_{n}b_{n-1}+a_n+a_{n-1}b_n/b_{n-2})f_{n-2}-a_{n-1}a_{n-2}b_n/b_{n-2}f_{n-4}$$

After the transformation we did, $b_i=1$ for all $i$ and $a_n=n(n-1)$ for $n>1$. Thus,
$$\begin{aligned}
f_n
&=(1+n(n-1)+(n-2)(n-1))f_{n-2}-(n-1)(n-2)^2(n-3)f_{n-4}\\
&=(2n^2-4n+3)f_{n-2}-(n-1)(n-2)^2(n-3)f_{n-4}
\end{aligned}$$

References:

Lorentzen, L. and Waadeland, H. (1992). Continued fractions with applications. Amsterdam ; London ; New York ; Tokyo: Elsevier Science Publishers B. V.

Pickett, T.J. and Coleman, A. (2008). Another Continued Fraction for π. The American Mathematical Monthly, 115(10), pp.930–933.

ContentLicense: CC BY-SA 4.0


问:
Basic questions about 2-sample t-test.
I am learning statistics so please bear with me in answering my questions. There is a common example in the statistics tutorials about the calorie content of the different brands of beef and poultry hotdogs.

Beef hotdogs: 186, 181, 176, 149, 184, 190, 158, 139, 175, 148, 152, 111, 141, 153, 190, 157, 131, 149, 135, 132

Poultry hotdogs: 129, 132, 102, 106, 94, 102, 87, 99, 170, 113, 135, 142, 86, 143, 152, 146, 144

The question is can it be inferred that the calorie content of poultry hotdogs is lower than the
calorie content of beef hotdogs with the significance level equals to 0.05?

To answer this, I initially calculated the mean and standard deviation of each sample and then used 2-sample t-test. I have some questions to ask:

To calculate $t_\alpha$, is it necessary to use Pooled Standard Deviation in other words which of the following formula should be used?

$t_\alpha = \frac{\mu_1 - \mu_2}{\sqrt{\frac{\sigma_1^2}{n_1} + \frac{\sigma_2^2}{n_2}}}$

or

$t_\alpha = \frac{\mu_1 - \mu_2}{s_p \sqrt{\frac{1}{n_1} + \frac{1}{n_2}}}$

I used both and noticed that the difference in the results was less than 0.1 and in this question this difference could be ignored but I wonder which is standard to use as I have seen the usage of both in the same situations in different tutorials?

To set $H_0$ and $H_1$, based on what question asks which of the following is correct:

$H_0$ :  "The calorie content of poultry hot dogs is not lower than the calorie content of beef hot dogs." and $H_1$ : "The calorie content of poultry hot dogs is lower than the calorie content of beef hot dogs."

$H_0$ : "There is no difference in the means of two samples." and $H_1$ : "There is a difference in the means of two samples."

I am asking this since the question is using the term "lower" and also there is a difference between the two bullet points. In the second bullet point, with $H_1$ when it is said there is a difference, this can be either "the calorie content of poultry hot dogs is lower than the calorie content of beef hot dogs" or "the calorie content of poultry hot dogs is greater than the calorie content of beef hot dogs." whereas in the first bullet point it $H_1$ clearly states "The calorie content of poultry hot dogs is lower than the calorie content of beef hot dogs." And I think these different types of setting $H_0$ determines whether to use one-tailed test or two-tailed one.

The question continues: "After mixing a certain food for calves, calories observed on the same sample of 17 brands of beef hotdogs as used above are:
181, 191, 186, 129, 178, 194, 139, 122, 195, 158, 158, 104,  132, 185, 168, 148, 123
Can it be inferred that mix of food has an effect in calorie of the beef hotdog?"

I think here obviously $H_0$ must be: mix of food has no effect and $H_1$ : mix of food has an effect

答:
Welch and pooled two-sample t tests. There are two kinds of two-sample t tests.

(a) The pooled test in which it is assumed that the two population variances are equal and the pooled variance is
$S_P^2 = \frac{(n_1-1)S_1$ + (n_2-1)S_2^2}{(n_1+n_2 - 2)},$ a degrees-of-freedom weighted average of the
two sample variances. This gives rise to your second
formula for the (pooled) t statistic. Under the null hypothesis the t statistic has Student's t distribution with $\nu = n_1+n_2-2$ degrees of freedom.

(b) By contrast, the Welch 2-sample t test does not assume that the two populations have the same variance.
This gives rise to your first formula for the (Welch) t statistic, in which the two variance estimates $S_1^2$ and $S_2^2$ are used separately. If $n_1 = n_2,$ one
can show that the two t statistics are equal.
However in the Welch test, under $H_0,$ the t statistic has approximately Student's t distribution with
$\nu^\prime$ degrees of freedom, where $\nu^\prime$ is determined by a formula containing $n_1, n_2, S_1^2, S_3^2$ giving $\min(n_1-1,n_2 -1) \le \nu^\prime \le n_1+n_2-2.$ (If $S_1^2\approx S_2^2,$ then $\nu^\prime$ is nearer the larger possible value.)

The Welch test is preferred unless we have substantial prior knowledge that $\sigma_1^2 \approx \sigma_2^2.$

One and two-sided alternatives. In R, for your initial hot dog data, the one-sided Welch t test for $H_0: \mu_b = \mu_p$ against $H_a: \mu_b > \mu_p$ looks as follows:

Data and description:

```<code>b = c(186, 181, 176, 149, 184, 190, 158, 139, 175, 148,
      152, 111, 141, 153, 190, 157, 131, 149, 135, 132)

p = c(129, 132, 102, 106, 94, 102, 87, 99, 170, 113,
      135, 142, 86, 143, 152, 146, 144)

summary(b); length(b);  sd(b)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
  111.0   140.5   152.5   156.8   177.2   190.0
[1] 20         # sample size beef
[1] 22.64201   # sample SD beef
summary(p); length(p);  sd(p)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
   86.0   102.0   129.0   122.5   143.0   170.0
[1] 17
[1] 25.48313

 boxplot(b, p, col="skyblue2", names=c("b","p"), label=T)
</code>```

One-sided Welch test: The P-value (near 0) shows that we can reject $H_0$ at
the 1% level of significance.

```<code>t.test(b, p, alt="g")  # parameter 'g'=greater (1-sided)

        Welch Two Sample t-test

data:  b and p
t = 4.3031, df = 32.394, p-value = 7.276e-05
alternative hypothesis:
 true difference in means is greater than 0
95 percent confidence interval:
 20.85096      Inf
sample estimates:
mean of x mean of y
 156.8500  122.4706
</code>```

Two-sided Welch test: If you test $H_0: \mu_b = \mu_p$ against the two-sided
alternative ("no difference" against "difference"), then the P-value is twice the P-value for
the one-sided test above--still very highly significant.
Also, for this test (without parameter alt = "g" will give a 95% CI with a lower and  upper bound for the difference between the two population means.

One-sided pooled test: Here is the pooled t test for the same data. Notice
that in R the Welch test is the default. If you feel
sure that the two population variances must be nearly equal, then you can do the pooled t test by using
the parameter var.eq=T. Notice that DF = 20 + 17 - 2 =35.

```<code>t.test(b, p, alt="g", var.eq=T)

        Two Sample t-test

data:  b and p
t = 4.3455, df = 35, p-value = 5.683e-05
alternative hypothesis:
 true difference in means is greater than 0
95 percent confidence interval:
 21.01239      Inf
sample estimates:
mean of x mean of y
 156.8500  122.4706
</code>```

Second data set. The analysis is similar and I will leave it to you. I think you are correct that you should do a two-sided test.

Title: Basic questions about 2-sample t-test.

Body:
Welch and pooled two-sample t tests. There are two kinds of two-sample t tests.

(a) The pooled test in which it is assumed that the two population variances are equal and the pooled variance is
$S_P^2 = \frac{(n_1-1)S_1$ + (n_2-1)S_2^2}{(n_1+n_2 - 2)},$ a degrees-of-freedom weighted average of the
two sample variances. This gives rise to your second
formula for the (pooled) t statistic. Under the null hypothesis the t statistic has Student's t distribution with $\nu = n_1+n_2-2$ degrees of freedom.

(b) By contrast, the Welch 2-sample t test does not assume that the two populations have the same variance.
This gives rise to your first formula for the (Welch) t statistic, in which the two variance estimates $S_1^2$ and $S_2^2$ are used separately. If $n_1 = n_2,$ one
can show that the two t statistics are equal.
However in the Welch test, under $H_0,$ the t statistic has approximately Student's t distribution with
$\nu^\prime$ degrees of freedom, where $\nu^\prime$ is determined by a formula containing $n_1, n_2, S_1^2, S_3^2$ giving $\min(n_1-1,n_2 -1) \le \nu^\prime \le n_1+n_2-2.$ (If $S_1^2\approx S_2^2,$ then $\nu^\prime$ is nearer the larger possible value.)

The Welch test is preferred unless we have substantial prior knowledge that $\sigma_1^2 \approx \sigma_2^2.$

One and two-sided alternatives. In R, for your initial hot dog data, the one-sided Welch t test for $H_0: \mu_b = \mu_p$ against $H_a: \mu_b > \mu_p$ looks as follows:

Data and description:

b = c(186, 181, 176, 149, 184, 190, 158, 139, 175, 148,
      152, 111, 141, 153, 190, 157, 131, 149, 135, 132)

p = c(129, 132, 102, 106, 94, 102, 87, 99, 170, 113,
      135, 142, 86, 143, 152, 146, 144)

summary(b); length(b);  sd(b)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
  111.0   140.5   152.5   156.8   177.2   190.0
[1] 20         # sample size beef
[1] 22.64201   # sample SD beef
summary(p); length(p);  sd(p)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
   86.0   102.0   129.0   122.5   143.0   170.0
[1] 17
[1] 25.48313

 boxplot(b, p, col="skyblue2", names=c("b","p"), label=T)

One-sided Welch test: The P-value (near 0) shows that we can reject $H_0$ at
the 1% level of significance.

t.test(b, p, alt="g")  # parameter 'g'=greater (1-sided)

        Welch Two Sample t-test

data:  b and p
t = 4.3031, df = 32.394, p-value = 7.276e-05
alternative hypothesis:
 true difference in means is greater than 0
95 percent confidence interval:
 20.85096      Inf
sample estimates:
mean of x mean of y
 156.8500  122.4706

Two-sided Welch test: If you test $H_0: \mu_b = \mu_p$ against the two-sided
alternative ("no difference" against "difference"), then the P-value is twice the P-value for
the one-sided test above--still very highly significant.
Also, for this test (without parameter alt = "g" will give a 95% CI with a lower and  upper bound for the difference between the two population means.

One-sided pooled test: Here is the pooled t test for the same data. Notice
that in R the Welch test is the default. If you feel
sure that the two population variances must be nearly equal, then you can do the pooled t test by using
the parameter var.eq=T. Notice that DF = 20 + 17 - 2 =35.

t.test(b, p, alt="g", var.eq=T)

        Two Sample t-test

data:  b and p
t = 4.3455, df = 35, p-value = 5.683e-05
alternative hypothesis:
 true difference in means is greater than 0
95 percent confidence interval:
 21.01239      Inf
sample estimates:
mean of x mean of y
 156.8500  122.4706

Second data set. The analysis is similar and I will leave it to you. I think you are correct that you should do a two-sided test.


问:
How to state Curry's Paradox in propositional logic?
Can Curry's Paradox be stated in propositional logic as:

$[A\iff [A\implies B]] \implies B$

This is a tautology.

Note that:

$[A\iff [A\implies B]] \equiv A\land B$

答:
You can try QSAT, in classical logic you get:

$$\vdash_C \forall P.(Q \leftrightarrow (Q \rightarrow P)) \rightarrow \forall P.P$$

One of the interesting challenges could be to show  the same in non-classical logic. It then depends how you read the propositional quantifier. If you only assume this distributivity (K-rule) of propositional quantifier in your non-classical logic:

$$\begin{array}{c}
 \hline
\vdash_M \forall P.(A \rightarrow B) \rightarrow (\forall P.A \rightarrow \forall P.B)\end{array}$$

and this introduction rule (N-rule):

$$\begin{array}{c}
 \vdash_M A \\
 \hline
 \vdash_M \forall P.A\end{array}$$

The non-classical logic could be minimal logic, because in minimal logic this here is derivable:

$$ \vdash_M(Q \leftrightarrow (Q \rightarrow P)) \rightarrow P$$

The rest would then follow from N-rule and K-rule in the corresponding propositional quantified minimal logic.


问:
Compute $\int_{0}^{1}\left[\frac{2}{x}\right]-2\left[\frac{1}{x}\right]dx$
The question is to find
$$\int_{0}^{1}\left(\left[\dfrac{2}{x}\right]-2\left[\dfrac{1}{x}\right]\right)dx,$$

where $[x]$ is the largest integer no greater than $x$, such as $[2.1]=2, \;[2.7]=2,\; [-0.1]=-1.$

Is there any nice method to solve this integral,Thank you everyone.

Some of my thoughts: I have if $a\in(0,1]$, then
$$\int_{0}^{1}\left[\dfrac{a}{x}\right]-a\left[\dfrac{1}{x}\right]dx=a\ln{a}.$$

What about $a>1$,
$$\int_{0}^{1}\left[\dfrac{a}{x}\right]-a\left[\dfrac{1}{x}\right]dx=?$$

and  $$\int_{0}^{1}\left(\left[\dfrac{2}{x}\right]-2\left[\dfrac{1}{x}\right]\right)^{2}dx=?$$

becasue I have
$$\int_{0}^{1}\left(\dfrac{1}{x}-\left[\dfrac{1}{x}\right]\right)^2=-1-\gamma+\ln{(2\pi)}$$

答:
$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\on}[1]{\operatorname{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$
\begin{align}
&\bbox[5px,#ffd]{\int_{0}^{1}\pars{%
\left\lfloor 2 \over x\right\rfloor -
2\left\lfloor 1 \over x\right\rfloor}\dd x}
\,\,\,\stackrel{x\ \mapsto\ 1/x}{=}\,\,\,
\int_{1}^{\infty}{%
\left\lfloor 2x\right\rfloor -
2\left\lfloor x\right\rfloor\, \over x^{2}}\,\dd x
\\[5mm] = &\
\lim_{N \to \infty}\pars{%
\int_{1}^{N}{\left\lfloor 2x\right\rfloor \over x^{2}}\,\dd x -
2\int_{1}^{N}{\left\lfloor x\right\rfloor \over x^{2}}\,\dd x}
\\[5mm] = &\
2\lim_{N \to \infty}\pars{%
\int_{2}^{2N}{\left\lfloor x\right\rfloor \over x^{2}}\,\dd x -
\int_{1}^{N}{\left\lfloor x\right\rfloor \over x^{2}}\,\dd x}
\\[5mm] = &\
2\lim_{N \to \infty}\pars{%
\int_{N + 1}^{2N}{\left\lfloor x\right\rfloor \over x^{2}}\,\dd x -
\int_{1}^{2}{\left\lfloor x\right\rfloor \over x^{2}}\,\dd x}
\\[5mm] = &\
-1 + 2\lim_{N \to \infty}\,\,\,
\sum_{k = N + 1}^{2N - 1}\,\,\,\int_{k}^{k + 1}{\left\lfloor x\right\rfloor \over x^{2}}\,\dd x =
-1 + 2\lim_{N \to \infty}\,\,\,
\sum_{k = N + 1}^{2N - 1}\,\,{1 \over k + 1}
\\[5mm] = &\
-1 + 2\lim_{N \to \infty}\,\,\,
\sum_{k = N + 2}^{2N}\,\,{1 \over k} =
-1 + 2\lim_{N \to \infty}\,\,\,
\pars{H_{2N} - H_{N - 1}}
\\[5mm] = &\
\bbx{2\ln\pars{2} - 1} \approx 0.3863 \\ &
\end{align}


问:
How to read and execute $\sum_{1 \leq \ell <m<n} \frac{1}{5^{\ell}3^{m}2^{n}}$

How to read and execute this sum?
$$\sum_{1 \leq \ell <m<n} \frac{1}{5^{\ell}3^{m}2^{n}}$$

I am having trouble to understand where is my error.

The question does not say, but I am assuming that $\ell$ starts at $1$, $m$ at $2$, and so $n$ at $3$.

This is essential a product of pg:

$$\sum_{1 \leq \ell<m<n} \frac{1}{5^{\ell}3^{m}2^{n}} = \sum_{\ell=1}\frac{1}{5^{\ell}}\sum_{m=2}\frac{1}{3^{m}}\sum_{n=3}\frac{1}{2^{n}} = \frac{1/5}{1-1/5}\frac{1/9}{1-1/3}\frac{1/8}{1-1/2}$$
But this does not agree with the answer :/

答:
The index region of the sum
\begin{align*}
\sum_{\color{blue}{1\leq \ell <m<n}}\frac{1}{5^{\ell}3^m2^n}\tag{1}
\end{align*}
is specified by the inequality chain
\begin{align*}
1\leq \ell <m<n
\end{align*}
which has $1$ as lower limit and $n$ as upper limit. We have two indices $\ell$ and $m$, which means we can write it as double sum as shown in the evaluation below.

We obtain
\begin{align*}
\color{blue}{\sum_{1\leq \ell <m<n}\frac{1}{5^{\ell}3^m2^n}}
&=\frac{1}{2^n}\sum_{\ell = 1}^{n-2}\frac{1}{5^{\ell}}\sum_{m=\ell+1}^{n-1}\frac{1}{3^m}\tag{2}\\
&=\frac{1}{2^n}\sum_{\ell = 1}^{n-2}\frac{1}{5^{\ell}}\left(\frac{\left(\frac{1}{3}\right)^{l+1}-\left(\frac{1}{3}\right)^n}{1-\frac{1}{3}}\right)\tag{3}\\
&=\frac{1}{2^n}\sum_{\ell = 1}^{n-2}\frac{1}{5^l}\,\frac{1}{2}\left(\frac{1}{3^l}-\frac{1}{3^{n-1}}\right)\tag{4}\\
&= \frac{1}{2^{n+1}}\sum_{l=1}^{n-2}\frac{1}{15^l}- \frac{1}{2^{n+1}\,3^{n-1}}\sum_{l=1}^{n-2}\frac{1}{5^l}\\
&=\frac{1}{2^{n+1}}\left(\frac{\frac{1}{15}-\left(\frac{1}{15}\right)^{n-1}}{1-\frac{1}{15}}\right)-\frac{1}{2^{n+1}\,3^{n-1}}\left(\frac{\frac{1}{5}-\left(\frac{1}{5}\right)^{n-1}}{1-\frac{1}{5}}\right)\tag{5}\\
&=\frac{1}{2^{n+2}\cdot7}\left(1-\frac{1}{15^{n-2}}\right)-\frac{1}{2^{n+3 }\,3^{n-1}}\left(1-\frac{1}{5^{n-2}}\right)\\
&\,\,\color{blue}{=\frac{1}{2^{n+2}\cdot7}-\frac{1}{2^{n+3}\,3^{n-1}}+\frac{1}{2^{n+3}\,3^{n-1}\,5^{n-2}\cdot7}}
\end{align*}

Comment:

In (2) we factor out $\frac{1}{2^n}$ and reorder the double sum using another common style.

In (3) we evaluate the inner sum using the finite geometric summation formula.

In (4) we do a simplification and multiply out in the next line.

In (5) we apply the finite geometric summation formula twice and do a simplification in the following lines.

Note: A varying upper limit $n$ is not admissible in your case. Here $n$ is a free variable whereas the indices $\ell$ and $m$ are bound variables. This is different to the situation
\begin{align*}
\sum_{1\leq \ell <m<n\color{blue}{<\infty}}\frac{1}{5^{\ell}3^m2^n}
\end{align*}
where $n$ is bound by the upper limit $\infty$ and where $n$ varies between $m$ and $\infty$.

Hint: You might find chapter 2: Sums in Concrete Mathematics by R.L. Graham, D.E. Knuth and O. Patashnik helpful. It provides a thorough introduction in the usage of sums.


问:
If $x \leq g(x) \leq x^2-x+1$ where $x \in [0,2]$, can we say that $g(x)$ is continuous at $x=1$?
If $x \leq g(x) \leq x^2-x+1$ where $x \in [0,2]$, can we say that $g(x)$ continuous at $x=1$ ?

Is $g(x)$ continuous in $[0,2]$?

答:
For the second one: Assume there is a continues $g(x)$ in $[0,2]$
that satisfy $${x\leq g(x)\leq x^{2}-x+1}$$ note that this
imply $$0.5\leq g(0.5)\leq0.25-0.5+1=0.75$$

Consider $\widehat{g}:[0,2]\to\mathbb{R}$ s.t $\widehat{g}(x)=g(x)$
for all $x\neq0.5$ and such that $$\widehat{g}(0.5)=g(x)+\delta$$
where $\delta\neq0$ is some number such that the above inequality
holds.

Then $\widehat{g}$ satisfy the above inequality but is not continues

ContentLicense: CC BY-SA 3.0


问:
Prove distance generates the product topology of $\mathbb{N}$ x $\mathbb{N}$ ... with discrete topology on each $\mathbb{N}$
I have that $X_i = \mathbb{N}$ for $i = 1,2...$ and let $\tau$ be the discrete topology in $\mathbb{N}$. In the set $X_1 \times X_2 \times ...$ we define the metric d:

$
d((i_1,i_2...), (j_1,j_2...)) = \begin{cases}
\frac{1}{n} \text{ if }i_n \neq j_n \text{ and } i_k = j_k \text{ for } k<n \\
0 \text{ if } i_k = j_k \text{ } \forall k
\end{cases}
$

I have to prove this metric generates the Cartesian product topology in $X_1 \times X_2 \times ...$ I really don't know how to approach this problem, as I tried imagining the open balls but haven't found the way to use it to my advantage.

答:
HINT: Let the product be $X$. Verify that if

$$x=\langle x_n:n\in\Bbb Z^+\rangle,y=\langle y_n:n\in\Bbb Z^+\rangle\in X\,,$$

then $d(x,y)<\frac1n$ if and only if $x_k=y_k$ for $k=1,\ldots,n$. Thus, if for each $x\in X$ and $n\in\Bbb Z^+$ we let

$$B_n(x)=\{y\in X:y_k=x_k\text{ for }k=1,\ldots,n\}\,,$$

then

$$B_d\left(x,\frac1n\right)=B_n(x)$$

for each $x\in X$ and $n\in\Bbb Z^+$. Let

$$\mathscr{B}=\left\{B_d\left(x,\frac1n\right):x\in X\text{ and }n\in\Bbb Z^+\right\}\,;$$

you know that $\mathscr{B}$ is a base for the metric topology on $X$, and we’ve just shown that

$$\mathscr{B}=\{B_n(x):x\in X\text{ and }n\in\Bbb Z^+\}\,.$$

so all you need to do to finish the proof is show that $\mathscr{B}$ is a base for the product topology on $X$. This requires a little work but is pretty straightforward.


问:
Integer Linear Programming Conditional Constraints
How can I create a constraint that reflects the following: if $x_{ij} = 1$ AND $x_{jk} = 1$ THEN $x_{ik} = 1$?

All my variables $x_{ij}$ are binary. To provide some context:

I'm trying to create a linear equation system to be solved via the simplex algorithm that provides a solution to the problems schools face when creating class groups. Each student chooses 5 other students that he would like to be with in the following year. The school promises that each student will be in a class with at least one of the students they chose. To create the equation system I decided that my variables will be boolean and represent the following: $x_{ij} = 1$ if student $i$ is with student $j$ and $x_{ij} = 0$ otherwise. Thus, $x_{ij}= x_{ji}$ and $x_{ii} = 1$.

However, I'm having trouble with the following constraint: if student $i$ is together with student $j$ and student $j$ is together with student $k$, then inevitably student $i$ will be together with student $k$. This is represented by the constraint I mentioned at the beginning of the question.

I tried using the big M approach as mentioned in other questions but to no avail. In these questions there was only one condition but I have two.

Even if I solve this problem, how can this be scalable? For example: if $x_{12} = x_{23} = x_{14} = 1$ then $x_{13} = x_{34} = x_{24} = 1$. Maybe the variables I chose are not correct and I'm overcomplicating things. If this is the case, any guidance in the right direction would be more than welcomed.

Thanks for the help in advance!

答:
Transitivity can be handled in the following way:

$$(1−x_{i,j}) + (1−x_{j,k}) \ge (1−x_{i,k})\tag{1}$$

as explained for example in paragraph $2.2$ of this reference.

I would like to add that (1), expressed under the equivalent form:

$$x_{i,j}+x_{j,k}-x_{i,k} \leq 1$$

possesses an equivalent logical formulation  (have you some practice of Prolog language ?) under the following "Horn clause":

$$\lnot x_{i,j} \lor \lnot x_{j,k} \lor x_{i,k}$$

(see pages 11 and 12 of this reference ).

Remark: nothing surprizing in fact because this clause expresses the fact that:

$$x_{i,j} \ \& \ x_{j,k} \ \implies \ x_{i,k}$$

I have personnally been programming with Prolog ; unlike its reputation (under the condition to use good implementations like SWI-Prolog), it can be an efficient alternative for working on boolean variables if one hasn't too much of them...


问:
question about a proof involving nonarchimedian fields Nakayama's lemma
If $K$ is a nonarchimedian field with integer ring $O_K$ whose maximal ideal is $\mathfrak{m}$ and residue field $k$. Let $\pi \in \mathfrak{m}$ (not necessarily a uniformizer as we are not assuming $O_K$ is a DVR) and $f, g \in O_K[X]$ are such that there exists $a, b \in O_K[X]$ $af+bg-1 \in \mathfrak{m}[x]$, why is $(O_K/\pi)[X]/(f,g)$ finitely generated as an $O_K/\pi$-module?

I'm really trying to understand this proof (from notes by Richard Crew on local class field theory) so any explanation or alternative proof about it is welcome.

答:
If you meant that $K$ has a real valued non-archimedian valuation $v$ and $O_K=\{s\in K,v(s)\ge 0\}$ then let $w(\sum_{n=0}^d c_n x^n)=\inf_n v(c_n)$, note that $w(uv)\ge w(u)+w(v)$ (in fact it is an equality).

$af+bg-1 \in \mathfrak{m}[x]$ gives that $w(af+bg-1)>0$ so there is some $r$ such that $w((af+bg-1)^r)\ge v(\pi)$ ie. $(af+bg-1)^r\in (\pi)$.

Thus $$O_K/(\pi)[x]/(f,g)=O_K/(\pi)[x]/(f,g,(af+bg-1)^r)=O_K/(\pi)[x]/(f,g,1)=0$$


问:
Question about repeating decimal?
For simple fraction, we can easily convert it to repeating decimal by calculator. Ex. $\frac 1 3 = 0.33333\ldots$, $\frac 1 7=0.(142857),\ldots$ But some fraction fraction like $10/29, 1/97,...$ The repeating part of them are too long, so it can't fully show on the calculator. So is there any algorithm  to find the repeating part for that fraction?</p>

答:
Yes. Here is one I once wrote in the R language.
It uses the 'gmp' (GNU Multiple Precision) package.</p>
```<code>#########################################################
### Functions for converting back and forth between   ###
### rational numbers and decimals. Repeating decimals ###
### are denoted by brackets around the digit block    ###
### repeats. For example, 11/6 is 1.8[3] in decimal.  ###
#########################################################

#############################
### Author: Roman Chokler ###
#############################
library(gmp)

bigq.to.dec <- function(q)
{
  sgn <- sign(q)
  num <- abs(numerator(q))
  den <- denominator(q)
  d <- den
  c2 <- 0
  c5 <- 0
  while(d %% 2==0)
  {
    d <- as.bigz(d/2)
    c2 <- c2 + 1
  }
  while(d %% 5==0)
  {
    d <- as.bigz(d/5)
    c5 <- c5 + 1
  }
  transient <- max(c2,c5)
  dec <- as.character(as.bigz(num/den))
  rem <- num %% den
  if (rem != 0)
  {
    dec <- paste0(dec,".")
    if (transient>0)
    {
      for(i in 1:transient)
      {
        rem <- rem * 10
        dec <- paste0(dec,as.bigz(rem/den))
        rem <- rem %% den
      }
    }
    if (rem != 0)
    {
      dec <- paste0(dec,"[")
      r <- rem
      rem <- rem * 10
      dec <- paste0(dec,as.bigz(rem/den))
      rem <- rem %% den
      while (rem != r)
      {
        rem <- rem * 10
        dec <- paste0(dec,as.bigz(rem/den))
        rem <- rem %% den
      }
      dec <- paste0(dec,"]")
    }
  }
  if (sgn == -1)
  {
    dec <- paste0("-",dec)
  }
  return(dec)
}

dec.to.bigq <- function(dec)
{
  bq <- 0
  sgn <- 1
  n <- nchar(dec)
  if (regexpr("-",dec)[1]==1)
  {
    sgn <- -1
    dec <- substr(dec,2,n)
    n <- n - 1
  }
  pnt <- regexpr("\\.",dec)[1]
  rstart <- regexpr("\\[",dec)[1]
  rend <- regexpr("\\]",dec)[1]
  if (pnt == -1)
  {
    return(as.bigq(dec) * sgn)
  }
  if (n==pnt)
  {
    return((as.bigq(substr(dec,1,pnt-1))) * sgn)
  }
  bq <- as.bigq(substr(dec,1,pnt-1))
  if (rstart == -1)
  {
    transient <- substr(dec,pnt+1,n)
    den <- pow.bigz(10,nchar(transient))
    transient <- sub("^0+","",transient)
    if (transient == "")
    {
      transient <- "0"
    }
    return((bq + div.bigq(transient,den)) * sgn)
  }
  den <- as.bigz(1)
  if (rstart > pnt + 1)
  {
    transient <- substr(dec,pnt+1,rstart-1)
    den <- pow.bigz(10,nchar(transient))
    transient <- sub("^0+","",transient)
    if (transient == "")
    {
      transient <- "0"
    }
    bq <- bq + div.bigq(transient,den)
  }
  if ((rend == -1) || (rstart >= rend - 1) || n > rend)
  {
    return(as.bigq(NA))
  }
  rep <- substr(dec,rstart+1,rend-1)
  den <- den * (pow.bigz(10,nchar(rep)) - 1)
  rep <- sub("^0+","",rep)
  if (rep == "")
  {
    rep <- "0"
  }
  return((bq + div.bigq(rep,den)) * sgn)
}
</code>```

Title: Question about repeating decimal?

Body:
Yes. Here is one I once wrote in the R language.
It uses the 'gmp' (GNU Multiple Precision) package.

#########################################################
### Functions for converting back and forth between   ###
### rational numbers and decimals. Repeating decimals ###
### are denoted by brackets around the digit block    ###
### repeats. For example, 11/6 is 1.8[3] in decimal.  ###
#########################################################

#############################
### Author: Roman Chokler ###
#############################
library(gmp)

bigq.to.dec <- function(q)
{
  sgn <- sign(q)
  num <- abs(numerator(q))
  den <- denominator(q)
  d <- den
  c2 <- 0
  c5 <- 0
  while(d %% 2==0)
  {
    d <- as.bigz(d/2)
    c2 <- c2 + 1
  }
  while(d %% 5==0)
  {
    d <- as.bigz(d/5)
    c5 <- c5 + 1
  }
  transient <- max(c2,c5)
  dec <- as.character(as.bigz(num/den))
  rem <- num %% den
  if (rem != 0)
  {
    dec <- paste0(dec,".")
    if (transient>0)
    {
      for(i in 1:transient)
      {
        rem <- rem * 10
        dec <- paste0(dec,as.bigz(rem/den))
        rem <- rem %% den
      }
    }
    if (rem != 0)
    {
      dec <- paste0(dec,"[")
      r <- rem
      rem <- rem * 10
      dec <- paste0(dec,as.bigz(rem/den))
      rem <- rem %% den
      while (rem != r)
      {
        rem <- rem * 10
        dec <- paste0(dec,as.bigz(rem/den))
        rem <- rem %% den
      }
      dec <- paste0(dec,"]")
    }
  }
  if (sgn == -1)
  {
    dec <- paste0("-",dec)
  }
  return(dec)
}

dec.to.bigq <- function(dec)
{
  bq <- 0
  sgn <- 1
  n <- nchar(dec)
  if (regexpr("-",dec)[1]==1)
  {
    sgn <- -1
    dec <- substr(dec,2,n)
    n <- n - 1
  }
  pnt <- regexpr("\\.",dec)[1]
  rstart <- regexpr("\\[",dec)[1]
  rend <- regexpr("\\]",dec)[1]
  if (pnt == -1)
  {
    return(as.bigq(dec) * sgn)
  }
  if (n==pnt)
  {
    return((as.bigq(substr(dec,1,pnt-1))) * sgn)
  }
  bq <- as.bigq(substr(dec,1,pnt-1))
  if (rstart == -1)
  {
    transient <- substr(dec,pnt+1,n)
    den <- pow.bigz(10,nchar(transient))
    transient <- sub("^0+","",transient)
    if (transient == "")
    {
      transient <- "0"
    }
    return((bq + div.bigq(transient,den)) * sgn)
  }
  den <- as.bigz(1)
  if (rstart > pnt + 1)
  {
    transient <- substr(dec,pnt+1,rstart-1)
    den <- pow.bigz(10,nchar(transient))
    transient <- sub("^0+","",transient)
    if (transient == "")
    {
      transient <- "0"
    }
    bq <- bq + div.bigq(transient,den)
  }
  if ((rend == -1) || (rstart >= rend - 1) || n > rend)
  {
    return(as.bigq(NA))
  }
  rep <- substr(dec,rstart+1,rend-1)
  den <- den * (pow.bigz(10,nchar(rep)) - 1)
  rep <- sub("^0+","",rep)
  if (rep == "")
  {
    rep <- "0"
  }
  return((bq + div.bigq(rep,den)) * sgn)
}


答:
This is indeed a metric on $\mathbb N^ \mathbb N$ (for the triangle inequality, show that $d(x,y) \leq \max \{ d(x,z),d(z,y)\}$ ). It's not hard to see that
$$ d(x,y) = \begin{cases}  0  \text{ if } x=y\\ \frac{1}{\min{ \{ n\in \mathbb N  \colon \ x(n) \neq y(n)  \} } }
\end{cases}$$
for any $x=(x (n) )$ and $y=(y(n))$. Furthermore, a sequence $(x_n)$ converges to a point $x $, with respect to $d$ if and only if for any $k \in \mathbb N$, there exists $n_0 \in \mathbb N$ such that for $n \geq n_0$, the initial $k-$segment of $(x_n)$ is identical to that of $x$. In other words, for any $k$, it's true that   $ x_n(1) =x(1), \cdots,  x_n(k)=x(k)$ eventually.

It is known that a countable product of first countable spaces is first countable (with the product topology). In fact, we can say more: the countable product of metric spaces is a metrizable space, thus $\mathbb N^\mathbb N$ is actually metrizable with the product topology.

So, in order to show that the product topology is the same as the one generated by the metric $d$, it suffices to show that they have the same convergent sequences. To this end, let $x_n \xrightarrow{d}x $ and let $U= V_1 \times V_2 \times \cdots \times V_k \times \mathbb N^{\mathbb N \setminus \{ k\} } $ be an open set in the product topology that contains $x$. We want to show that  $x_n \in V$ eventually, or equivalently, $x_n(1) \in V_1,  \cdots, x_n(k) \in V_k$ eventually. This is true however, since by the metric convergence, $x_n(1) =x(1), \cdots ,x_n(k) =x(k)$ eventually.

On the other hand, if $x_n \to x$ in the product topology, then for any given  $ε>0$, we can find a $k \in \mathbb N$ such that $1/k<ε$ and since the set $V= \{ x(1) \} \times \cdots \times \{ x(k) \} \times \mathbb N^{\mathbb N \setminus \{k \}} $ is open in the product topology and it contains $x$, it must be true that $x_n \in V$ eventually. Hence, $x_n(1) =x(1), \cdots ,x_n(k) =x(k) $ eventually and so $ \{ m \in \mathbb N \colon \ x_n(m) \neq x(m) \} \geq k$, or equivalently, $ d(x_n,x) < ε$.

Title: Prove distance generates the product topology of $\mathbb{N}$ x $\mathbb{N}$ ... with discrete topology on each $\mathbb{N}$

Body:
I have that $X_i = \mathbb{N}$ for $i = 1,2...$ and let $\tau$ be the discrete topology in $\mathbb{N}$. In the set $X_1 \times X_2 \times ...$ we define the metric d:

$
d((i_1,i_2...), (j_1,j_2...)) = \begin{cases}
\frac{1}{n} \text{ if }i_n \neq j_n \text{ and } i_k = j_k \text{ for } k<n \\
0 \text{ if } i_k = j_k \text{ } \forall k
\end{cases}
$

I have to prove this metric generates the Cartesian product topology in $X_1 \times X_2 \times ...$ I really don't know how to approach this problem, as I tried imagining the open balls but haven't found the way to use it to my advantage.


问:
Can these two definitions be proven equivalent without the axiom of choice?
By $Map(X,Y)$, I denote the set of functions from $X$ into $Y$. Consider $Map(X,X)$, and let $f$ and $g$ be elements of $Map(X,X)$. I define a relation "$g$ is a function of $f$", iff there exists a function $h \in Map(X,X)$, such that $h$ composed with $f$ equals $g$. My original definition, however, was "if $f(x)=f(y)$ then $g(x)=g(y)$, for all $x \in X$". These two definitions can be proven equivalent with the axiom of choice. However, what happens if we don't assume choice? Can it be proven equivalent in ZF alone? And if not, is the principle equivalent to choice over ZF, or strictly weaker than choice?

答: I'm not sure how the axiom of choice would be involved here.  Just define $h(a)$ to be the common value of $g(x)$ for all $x$ such that $f(x)=a$ (there is at most one such value of $g(x)$ by hypothesis), or define $h(a)$ arbitrarily (say, $h(a)=a$) if no such $x$ exists.


问:
Combinations, Expected Values and Random Variables
A community consists of $100$ married couples ($200$ people). If during a given year, $50$ of the members of the community die, what is the expected number of marriages that remain intact?

Assume that the set of people who die is equally likely to be any of the ${200 \choose 50}$ groups of size $50$

Hint: For $i = 1, ..., 100$ let $X_i$ $=$$\{1$, if neither member of couple $i$ dies; and $0$, otherwise$\}$

It's a question from "Probability and Statistics for Engineers and Scientists" by Sheldon Ross ... and I have no idea how to go about it. Any help would be greatly appreciated.

答:
Use the linearity of expectation. Let $X$ be the rv of the number of couples that survive. Then $$X = \sum_{i=1}^{100} X_i.$$

Thus,

$$E[X] = E[\sum_{i=1}^{100} X_i] = \sum_{i=1}^{100} E[X_i] = 100 E[X_1]. $$


问:
Variance of Brownian motion at jump points
How can one evaluate $Var(B(T_1))$, where $\{B(t), t \geq 0\}$ is a Standard Brownian motion and $\{T_n\}_{n \geq 1}$ denote the jump points of a Poisson($\lambda $) process?

答:
From comments to give an answer:

You can use the law of total variance

So you said $$Var(B(T_1)) = E(Var[B(T_1)\mid T_1]) + Var(E[B(T_1) \mid T_1]) = E[T_1] + 0 = 1/\lambda$$

which looks correct to me

As an empirical check using R:

```<code>set.seed(2020)
lambda <- 0.2
cases <- 10^6
T1 <- rexp(cases, rate=lambda)
B1 <- rnorm(cases, mean=0, sd=sqrt(T1))
var(B1)
# 5.000312
</code>```

Body:
From comments to give an answer:

You can use the law of total variance

So you said $$Var(B(T_1)) = E(Var[B(T_1)\mid T_1]) + Var(E[B(T_1) \mid T_1]) = E[T_1] + 0 = 1/\lambda$$

which looks correct to me

As an empirical check using R:

set.seed(2020)
lambda <- 0.2
cases <- 10^6
T1 <- rexp(cases, rate=lambda)
B1 <- rnorm(cases, mean=0, sd=sqrt(T1))
var(B1)
# 5.000312


问:
residue of $f(z)=\sqrt[3]{z^2(1-z)}$ at $\infty$
I'm trying to find the residue of $f(z)=\sqrt[3]{z^2(1-z)}$ at $\infty$, while computing $\int^1_0  \sqrt[3]{x^2(1-x)} dx$

I know that I can compute it using $g(w) = -w^{-2} f(1/w)$ at $w = 0$ (Residue at infinity, contradiction?).

So I have  $g(w)=\frac{-1}{w^2} \sqrt[3]{\frac {1}{w^2} (1-\frac{1}{w})}=\frac{-1}{w^2} \sqrt[3]{\frac {1}{w^3} (w-1)}$.

And here I don't know what to do. I want to put $\frac{1}{w^3}$ out of the root, can one do this? And why? And if not what one can do? Could you please help me to find the residue explicitly?

答:
The answer is that you can just pull $w^3$ out of the cube root because the ambiguity in $w$ is a phase factor of $e^{2\pi in}$ for some integer $n$, and when you cube it and take the cube root you still have $e^{2\pi in}=1$. The problem is that that's the easy part. The hard part is determining the phase of the cube root. Let's look at the original contour, as I assume is in your solution:

The little red circles mark out the branch points at $0$ and $1$. Here as the radii of the circles decrease towards $0$ the integral from $A$ to $B$ becomes the one you are trying to evaluate but as we travel clockwise from $B$ through $C$ and then to $D$ the phase of the cube root decreases by $e^{-2\pi i/3}$ so the integral around the contour, given that the integrals around the circles will shrink to $0$ as their radii do, will be
$$\oint_Cf(z)dz=\left(1-e^{-2\pi 1/3}\right)\int_0^1\sqrt[3]{z^2(1-z)}\,dz=2ie^{-\pi i/3}\sin(\pi/3)I=i\sqrt3e^{-\pi i/3}I$$
After the transformation $w=1/z$ the picture in the $w$-plane is as shown below:

At $B^{\prime}$ we hope the the phase of $w$ matches that of $z$ at $B$, hence both $0$ and the phase of the cube root should match as well. Since the phase at $C$ is $e^{-\pi i/3}$ then we have
$$\sqrt[3]{\frac{w-1}{w^3}}=\frac1w\sqrt[3]{(1-w)}e^{-\pi i/3}$$
So we see that the effective integrand will be
$$-\frac1{w^3}\sqrt[2]{1-w}e^{-\pi i/3}$$
And the residue at $0$ (marked with a black X) will be
$$\lim_{w\rightarrow0}\frac1{2!}\frac{d^2}{dw^2}\left(w^3\left(-\frac1{w^3}\sqrt[3]{(1-w}e^{-\pi i/3}\right)\right)=-\frac12\left(-\frac29\right)e^{-\pi i/3}=\frac19e^{-\pi i/3}$$
Since we circled the pole at zero counterclockwise in Figure 2, we have
$$i\sqrt3e^{-\pi i/3}I=2\pi i\left(\frac19e^{-\pi i/3}\right)$$
So our answer is that
$$I=\int_0^1\sqrt[3]{z^2(1-z)}dz=\frac{2\pi}{9\sqrt3}$$
As could have been determined more easily by recognizing the integral as a Beta function. Another thing you might have done is to consider that the answer has to be positive real so you could have ignored the phase of the cube root in the residue calculation and just taken the absolute value of whatever result you got, but that wouldn't have answered your question :)


问:
Every open connected set $S \subset \mathbb{R}^n$ is path-connected.
$\mathbf{Attempt:}$Consider the open cover $\bigcup_{x\in S} B(x,r_x)$    of $S$ with each $B(x,r_x)\subset S$ for some $r_x>0$.

We can invoke the Lindelöf property to get ourselves a countable subcover $\bigcup_{i\in \mathbb{N}} B(x_i,r_{x_i})$    of $\bigcup_{x\in S} B(x,r_x)$ which still covers $S$.
We know that every ball $B(x,r_x)=\{y\in \mathbb{R}^n: d(x,y)<r_x\}\subset S$ is path connected.

$\underline{Claim:}$ The union over a family of non-empty path-connected sets $\{A_i\}_{i\in I_n}$ remains path-connected if for $k =1,2,...,n-1$

$\displaystyle(\bigcup_{i\in I_n\setminus J_k}A_i)\bigcap (\bigcup_{t\in J_k} A_t)\neq \emptyset$

$\forall n \geq 2$, where $I_n=\{1,2,...,n\}$ and $J_k=\{s_1,s_2,...,s_k\}\subset I_n$ where $s_i$ takes arbitrary value and $s_i \neq s_j$ for any two $i\neq j$.

$\underline{Justification:} $
For $n=2$, consider $A_1$ and $A_2$ to be two path connected sets with non-empty intersection. Pick any two $a,b \in A_1 \cup A_2$. For $a,b \in A_1$ or $a, b \in A_2$ we can find readily find a path connecting them within that set.
Now, for $a \in A_1$ and $b\in A_2$ (WLOG), define $h:[0,1] \to A_1\cup A_2$ such that $h(t)=f(2t)$ for $t \in [0,1/2]$ and $h(t)=g(2t-1)$ for $t \in [1/2,1]$ where $f:[0,1] \to A_1$ and $g:[0,1] \to A_2$ such that $f(0)=a$ and $f(1)=c$ and $g(0)=c$ and $g(1)=b$, $c \in A_1\cap A_2$. Clearly, $h$ is continuous on $[0,1]$ with $h(0)=a$ and $h(1)=b$. Hence $A_1 \cup A_2$ is path connected.

Let for $n=m$, $\displaystyle(\bigcup_{i\in I_m\setminus J_k}A_i)\bigcap (\bigcup_{t\in J_k} A_t)\neq \emptyset$.

Put $J_1=1$. Then we get at least one $r_1\neq 1$ such that $A_1\cap A_{r_1}\neq \emptyset$, i.e $A_1 \cup A_{r_1}$ is path connected. Next, let us set $J_2=\{1,r_1\}$. We get $r_2\neq 1, r_1$ with $A_{r_2}\cap(A_1\cup A_{r_1}) \neq \emptyset$. So $A_1\cup A_{r_1}\cup A_{r_2}$ is path connected.

Iterating this process until we exhaust all of $I_m$, we find that $\bigcup_{I_m} A_i$ remains path-connected. This argument holds for $m$, $m+1$ $\cdots$. So for any such countable family, it holds good as well.

Going back to our countable open cover of $S$, we must have $\displaystyle(\bigcup_{i\in \mathbb{N}\setminus J_k}B(x_i,r_{x_i}))\bigcap (\bigcup_{t \in J_k} B(x_t,r_{x_t}))\neq \emptyset$, for all $k\in \mathbb{N}$ and any $J_k$. [Otherwise its emptiness would give us $C=\bigcup_{i\in \mathbb{N}\setminus J_k}B(x_i,r_{x_i})$ and $D=\bigcup_{t\in J_k}B(x_t,r_{x_t})$ for some $J_k$ corresponding to some $k$, such that $C\cap D=\emptyset$ and $C\cup D = S$, both of which are open in the subspace metric on $S$, implying that $S$ is disconnected].

We can now establish the path-connectedness of $S\subset \mathbb{R}^n$ by appealing to our pre-verified claim and choosing $A_i=B(x_i,r_{x_i})$.

$\text{Is this okay? Kindly Verify}.$

答:
I didn't read the whole proof, but it seems like it could work, but it is definitely not the "best" way to show the desired result, it just uses way too much machinery, using Lindelof's theorem and the way of showing that the thing you're constructing is path connected.

I'm not sure if you've seen the definition of locally path connected, but it reads:

$X$ is locally path connected if for all $p \in X$, for every open $U$ s.t. $x \in U$ there exists $V \subseteq U$ s.t. $V$ is open, $x \in V$, and $V$ is path connected.

Now you should be able to easily convince yourself that $\mathbb{R}^n$ is locally path connected. Then convince yourself that open subsets of locally path connected spaces are locally path connected in the subspace topology. So now if $U \subseteq \mathbb{R}^n$ is open, then $U$ is locally path connected. Then suppose (as in your problem) that $U$ is also connected, we want to show it is path connected. Here is  an example of a proof that connected and locally path connected spaces are path connected, which will finish the proof of your result. Note that the result that connected, locally path connected spaces are path connected is (almost) immediate from the result that path components of locally path connected spaces are open, which isn't hard to show, so you could also show it that way.


问:
General form to standard form conics with xy non-zero?
Let be the general equation of a conic \begin{align*}Ax^2+Bxy+Cy^2+Dx+Ey+F=0\end{align*} with \begin{align*}B \neq 0 \end{align*} What is the most effective way to transform this general equation into a standard equation, considering the perspective of a software implementation because I need to draw the conic on a screen and displaying its properties?

答:
https://i.stack.imgur.com/ak1TL.png

It is import to note the above before any calculations are conducted. Now, I personally have not come across any conic general equation where Bxy exists, so I cannot help you there. However, when Bxy = 0, I can help. To convert, move F to the other side and complete the square on Dx and Ey, then factorise. The factorisation part may be difficult to program , but implementing functions into the code should help. Then, to draw, the number on the right hand side is the radius squared, and the centre (h, k) will be represented on the Left hand side as $(x-h)^2 + (y-k)^2 = r^2$.


问:
Sum of Lebesgue measure
We let $m_{I}$ be the Lebesgue-measure on $(\mathbb{R},\mathcal{B})$
restricted to the interval $I=(0,1)$ which means $m_{I}=m((0,1)\cap A), A\in\mathcal{B}$. We assume that is proved that $m_{I}$ is a measure.

Now we define the measure $\mu=\sum^{\infty}_{n=1}m_I$. Then I have to find a expression for $\mu(A)$.

I think we get:
$$\mu(A)=\begin{cases}
0, & \text{if }m_{I}=0 \\
\infty, & \text{if }m_{I}>0
\end{cases}$$
because if $m_{I}=0$ then we got a sum over $0$ and it is just $0$. And if $m_{I}>0$ then we got a sum over a interval (because we have a Lebesgue measure we got a positive number), and then we get that $\mu(A)=\infty$ if $m_{I}>0$. I think the expression for $\mu(A)$ is correct, but I'm not sure how to "prove" it? Can anyone help me?
I have only used intuitive thoughts but how will you show it?

答: This does not require any Measure Theory. If $a \geq 0$ and $a_n=a$ for all $n$ then $\sum a_n =\infty$ if $a>0$ and $0$ if $a=0$. To prove this just calculate the partial sums and take the limit.

Title: Sum of Lebesgue measure


问:
Proof that a non-negative quadratic equation has at most one solution without using calculus
I'm working through Lax and Terrell's 'Calculus with Applications'. One of the first exercises is to work through the proof of the Cauchy-Schwarz inequality (without calculus). I'm all good for my proof except for the first part: i.e., how do I prove that a non-negative quadratic equation has at most one solution?

I can 'explain' this geometrically, i.e., a non-negative quadratic equation can only have a solution where the vertex touches the X axis. However, this doesn't feel very 'rigorous'.

Is there a better, algebraic, proof I could use here?

Thank you!

答:
Suppose that $f(x):= ax^2 + bx + c \geq 0$ for every $x \in \mathbb{R}$ and that there exist $x_1,x_2, x_1 \ne x_2$ s.t. $f(x_1) = f(x_2) = 0$. Then, by polynomial long division, $f(x) = (x-x_1)q(x) + r(x)$ where $r(x)$ has degree $0$ and $q(x)$ has degree $1$. But then $0= 0f(x_1) = 0q(x) + r(x_1) = r(x_1)$. So $r(x_1) = 0$, but $r(x) = d$ for some $d \in \mathbb{R}$ (since it has degree $0$), so $d = 0$. Thus $f(x) = (x-x_1)q(x)$. Then $q(x) = ux-v$ for some $u,v \in \mathbb{R}$. Also $0=f(x_2)= (x_2 - x_1)q(x_2)$. Then $x_2 - x_1 \ne 0$, by assumption, so $q(x_2) = 0$. Thus $ux_2 - v= 0$, or $v = ux_2$. But then
$$f(x) = (x-x_1)(ux+v) = ux^2 +(v-ux_1)x -x_1v = ax^2 + bx+c,$$
so $u=a$, so  $v= ax_2$. Thus, putting it together,
$$f(x) = (x-x_1)(ax-ax_2) = a(x-x_1)(x-x_2).$$
Now let $x_3$ between $x_1$ and $x_2$ (we can without loss of generality suppose $x_1 <x_2$, so $x_1 < x_3 < x_2$). Then $x_3 - x_1 > 0$ and $x_3 - x_2 <0$, so $k:= (x_3-x_1)(x_3-x_2)<0$. Thus
$$f(x_3) = a(x_3 -x_1)(x_3-x_2) = ak$$
so $f(x_3)$ has the opposite sign of $a$ (since $k$ is strictly negative). Then by assumption, for all $x$, $f(x) \geq 0$, so $f(x_3)\geq 0$. Thus $a \leq 0$. Then let $x_4 >x_1, x_2$. Then $x_4-x_1, x_4 - x_2>0$, so $k' := (x_4-x_1)(x_4-x_2) >0$. So
$$f(x_4) = a(x_4-x_1)(x_4 -x_2) = ak'.$$
Then $a \leq 0$ and $k' \geq 0$, so $f(x_4) \leq 0$. But also, by assumption $f(x_4) \geq 0$. Thus $f(x_4) =0$. But $k' \ne 0$, so $a = 0$.

Thus
$$f(x) = bx +c,$$
but it is easy to see that this is nonnegative for all $x$ iff $b =0$. Thus $f(x) = c$, but $f(x_1) =0$, so $0 = f(x_1) = c$, so $f(x) = 0$. But we assumed that $f$ has only two roots, but $f(x) = 0$ has infinitely many roots, so we have a contradiction. Thus a nonnegative quadratic cannot have two roots. But any quadratic also has at most two roots, so a nonnegative quadratic has at most one root.


问:
Understanding what a differential is (Why can physicists multiply both sides by dx?)
I've just finished my first semi-rigorous run through single variable calculus, where I tried proving most of the results using epsilon-delta proofs. I'm just not sure that I'm understanding the meaning of differentials properly.

I learned that the derivative with respect to a variable was an operator, meaning it 'took in' a function and 'outputted' a function that has a value of $\lim_{h\to 0} \frac{f(x+h)-f(x)}{h}$ at all values of x where $f$ is differentiable. Based on this definition, $\frac{dy}{dx}$ is a function of x.

I also learned that when integrating or finding the antiderivative with respect to x, the dx within the integral represented the infinitely small width of an interval in a partition of a Darboux or Reimann sum.

When solving differential equations with separation of variables or integrating using u-substitution, I've seen people say things like 'multiply both sides by dx' or 'bring dt to the other side',  especially in physics. This doesn't sound right, because I'm not sure how multiplying a function ($\frac{dy}{dx}$) by an infinitesimal (dx) gives another infinitesimal. So I'm wondering if this is this just a notational shortcut for the chain rule, or saying things like $\frac{dy}{dx} dx = dy$ has some mathematical meaning.

答:
There are many instances where treating $dx$ as a number is convenient, and luckily, many times it can be at least partially justified. I'm sure your familiar with the 'proof' of the chain rule:
$$
\require{cancel}
\frac{dy}{du} \cdot \frac{du}{dx} = \frac{dy}{\cancel{du}} \cdot \frac{\cancel{du}}{dx} = \frac{dy}{dx} \, .
$$
While it is incorrect to naively view the chain rule as cancellation, I don't think this argument is that far off the truth. The chain rule can be more properly justified in the following way:
$$
\lim_{\Delta x \to 0}\frac{\Delta y}{\Delta x} = \lim_{\Delta x \to 0}\frac{\Delta y}{\Delta u} \cdot \frac{\Delta u}{\Delta x} = \lim_{\Delta x \to 0}\frac{\Delta y}{\Delta u} \cdot \lim_{\Delta x \to 0}\frac{\Delta u}{\Delta x} \, .
$$
It can then be shown that
$$
\lim_{\Delta x \to 0}\frac{\Delta y}{\Delta u} = \lim_{\Delta u \to 0}\frac{\Delta y}{\Delta u} \, .
$$
While even this argument sweeps some issues under the rug, the point remains that is often convenient to regard derivatives as fractions. And it shouldn't be too surprising that limits of fractions often behave just like fractions. It is clear that
$$
\lim_{h \to 0}\frac{f(x+h)-f(x)}{h} \approx \frac{f(x+h)-f(x)}{h}
$$
for small enough $h$. This means that $dy/dx$ can, roughly speaking, be viewed as the quotient of two tiny quantities, $dy$ and $dx$, which partially justifies the manipulation of them in an equation. There have been many attempts to formalise these heuristic arguments—for example, in nonstandard analysis. While I think most mathematicians will agree that none of these attempts have been entirely successful, it is reassuring to know that there is a framework that can turn these informal arguments into rigorous proofs.

$dy/dx$ can be viewed as an actual quotient in another sense, too. Say you plot the graph of $y=x^2$ and consider the gradient at a particular point $P$. If you move a certain distance along the tangent to $P$, going $dy$ units upwards and $dx$ units to the right, then $dy/dx$ should be exactly equal to $2x$. But if you 'zoom in' far enough, then moving along the tangent line looks no different to moving along the curve. This way of viewing $dy/dx$ as a quotient avoids the machinery of nonstandard analysis, while also being fairly intuitive in my opinion. This means that
$$
\frac{dy}{dx}=f'(x) \implies dy = f'(x)dx = \frac{dy}{dx}dx
$$
as you mentioned in your post. So $dx$ and $dy$ can be given a meaning as independent quantities, even though $dy/dx$ generally means 'apply the derivative operator, $\frac{d}{dx}$, to $y$'.

Regarding some of the other instances where you question the use of infinitesimals:

Integration by substitution

Integration by substitution comes from reversing the chain rule. Recall that if $y=f(g(x))$, then
$$
\frac{dy}{dx}=f'(g(x))g'(x) \, .
$$
Thus,
$$
\int f'(g(x))g'(x) \, dx = f(g(x))+C \, .
$$
On the other hand, if we make the substitutions $u=g(x)$ and $du = g'(x) \, dx$, then  the integral becomes
$$
\int f'(u) \, du=f(u)+C=f(g(x))+C \, .
$$
It just so happens that working out $du/dx$ and then 'multiplying by $du$' means that you will make the correct substitutions. The formula can be summarised as
$$
\int f(g(x))g'(x) \, dx = \int f'(u) \, du \quad \text{where $u=g(x)$}
$$
In Leibnizian notation, it reads particularly well
$$
\int \frac{dy}{du} \cdot \frac{du}{dx} \, dx = \int \frac{dy}{du} \, du \, .
$$
Again, the $dx$'s 'cancel' in a similar fashion to the chain rule.

Separating the variables

It is common to solve first order differential equations in the following way:
\begin{align}
\frac{dy}{dx} &= f(x)g(y) \\[4pt]
dy &= f(x)g(y)dx \\[4pt]
\frac{1}{g(y)} dy &= f(x) \, dx \\[4pt]
\int \frac{1}{g(y)} dy &= \int f(x) \, dx \\[4pt]
\end{align}
Although the steps we used do seem questionable, the conclusion we draw is not. It can be directly shown that
$$
\frac{dy}{dx} = f(x)g(y) \iff \int \frac{1}{g(y)} dy = \int f(x) \, dx \, .
$$
Here is how:
\begin{align}
&\int \frac{1}{g(y)} dy = \int f(x) \, dx \\[4pt]
\iff & \frac{d}{dx} \int \frac{1}{g(y)} dy = \frac{d}{dx} \int f(x) \, dx \\[4pt]
\iff & \frac{1}{g(y)} \cdot \frac{dy}{dx} = f(x) \\[4pt]
\iff & \frac{dy}{dx} = f(x)g(y) \, .
\end{align}
I'm not sure if there is a 'deeper' reason why $dx$ and $dy$ can be treated as manipulable quantities in this case. Perhaps others can shed some light on that.


问:
The weak type (1,1) estimate for the Hilbert transform
I'm reading proofs that $H$, the Hilbert transform, is weak-$(1,1)$, so I'd like to show that there is a constant $C>0$ such that

$$| \{|Hf| > \lambda\}| \le \frac{C}{\lambda} \|f\|_{L^1}$$
for all $\lambda > 0$ and  $f \in L^1([-\pi,\pi]).$

All the proofs start by assuming that $ \|f\|_{L^1} < \lambda$ , why it is enough to discuss this case only? Any justification please!

答:
Observe that for the inequality in question is equivalent to
$$
\left| \left\{ \left| H\left(\frac{f}{\|f\|_{L^1}}\right) \right| > \frac{\lambda}{ \|f\|_{L^1}} \right\} \right| \leq C \frac{\|f\|_{L^1} }{\lambda}.
$$
for all non-trivial functions $f\in L^1$. Now for $\lambda \geq \|f\|_{L^1}$, the right-hand side becomes larger, while the left-hand side becomes smaller. For this reasons, it suffices to prove that it for $\|f\|_{L^1} < \lambda$. In fact, by setting, $g= f / \lambda$, where $f \in L^1$ and $\lambda >0$, the weak-type inequality is equivalent to establishing that

$$
\left| \left\{ \left| H(g) \right| > 1 \right\} \right| \leq C
$$
for every $g \in L^1$ with $\|g\|_{L^1}=1$. In other words, it just a standard normalization using a scaling and homogeneity argument, which allows to "disregard" the parameter $\lambda >0$.


问:
Tensor product and extension of scalars
We have that $\mathbb{Z}^n\otimes_{\mathbb{Z}}\mathbb{Q}\cong \mathbb{Q}^n$. Now, consider an abelian group of the form
$$G = \mathbb{Z}^n\oplus\mathbb{Z}/p_1\mathbb{Z}\oplus\dots\oplus \mathbb{Z}/p_n\mathbb{Z}$$
Is the tensor product $G\otimes_{\mathbb{Z}}\mathbb{Q}$ still isomorphic to $\mathbb{Q}^n$? If so are the torsion elements in $G$ completely undetectable after tensoring by $\mathbb{Q}$?

答:
Yes and yes. This is a straightforward calculation using the fact that tensor products preserve colimits; we get that

$$A \otimes \mathbb{Q} \cong \mathbb{Q}^n \oplus \bigoplus_{i=1}^n \mathbb{Q}/p_i \mathbb{Q}$$

(using that tensor products preserve first direct sums and then cokernels). But $p_i \mathbb{Q} = \mathbb{Q}$ so $\mathbb{Q}/p_i\mathbb{Q} = 0$. (I've renamed the abelian group to $A$.)

In general, the kernel of $A \to A \otimes \mathbb{Q}$ is exactly the torsion subgroup of $A$. This has the following fun interpretation in homological terms. Tensoring any abelian group $A$ with the short exact sequence $0 \to \mathbb{Z} \to \mathbb{Q} \to \mathbb{Q}/\mathbb{Z} \to 0$ produces a Tor exact sequence

$$0 \to \text{Tor}_1(A, \mathbb{Q}/\mathbb{Z}) \to A \to A \otimes \mathbb{Q} \to A \otimes \mathbb{Q}/\mathbb{Z} \to 0$$

(since $\mathbb{Q}$ is flat) which shows that the kernel of $A \to A \otimes \mathbb{Q}$ is exactly $\text{Tor}_1(A, \mathbb{Q}/\mathbb{Z})$, which is therefore the torsion subgroup of $A$ (this is where "Tor" gets its name from). This calculation can also be done using the slightly easier fact that $\text{Tor}_1(A, \mathbb{Z}/n\mathbb{Z})$ is the $n$-torsion subgroup of $A$ (which follows from using the Tor exact sequence given by tensoring with $0 \to \mathbb{Z} \xrightarrow{n} \mathbb{Z} \to \mathbb{Z}/n\mathbb{Z} \to 0$), then taking a filtered colimit over all $n$ and using the fact that Tor preserves filtered colimits in each variable.

Title: Tensor product and extension of scalars


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

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

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

答:
Observations: data points of the form $(y_i, x_{i1}, \ldots, x_{ip})$ for $i = 1,\ldots,n$.

Probability model: conditional distribution of $y_i$ given $x_{i1},\ldots, x_{ip}$ is a normal distribution with mean $\beta_1 x_{i1} + \cdots + \beta_p x_{ip}$ and some variance, for some real coefficients $\beta_1, \ldots, \beta_p$.

Note that one can perform linear regression without any probabilistic assumptions. But the above formulation is the usual set of assumptions when discussing things like bias/variance of the model, inference of coefficients, etc.

Note also that the above conditions might vary in different contexts. For instance, the above only models the conditional distribution (effectively keeping the $x_{ij}$ fixed/known); some might model the $x_{ij}$ as random variables as well. Conditions on the variance may vary. Is it known or unknown? Is it constant for all $i$ (homoskedastic) or does it vary with $i$ (heteroskedastic)? What if you don't require the conditional distribution to be normal?


问:
Construct Unitary Matrix when one basis transformation is known
Is there a standard method for constructing a unitary matrix $U$ to create a target vector when applied to input vector $\begin{pmatrix}
1\\
0\\
0\\
0\\
\end{pmatrix}$ ?

For example, with this target state:

$\begin{pmatrix}
\frac{1}{\sqrt{2}}\\
0\\
0\\
\frac{1}{\sqrt{2}}\\
\end{pmatrix} = U\begin{pmatrix}
1\\
0\\
0\\
0\\
\end{pmatrix}$

I expect that the matrix $U$ must have the form:
$\begin{pmatrix}
\frac{1}{\sqrt{2}} & . & . & .\\
0 & . & . & .\\
0 & . & . & .\\
\frac{1}{\sqrt{2}} & . & . & .\\
\end{pmatrix}$

but I expect there to be many ways of constructing the matrix, because I haven't specified what must happen to other basis vectors when undergoing the transformation.

I know that for my example, this is a valid matrix. However, I obtained this by starting from a quantum computing circuit. I wouldn't have got to it from my original problem statement alone:

$\begin{pmatrix}
\frac{1}{\sqrt{2}} & 0 & \frac{1}{\sqrt{2}} & 0\\
0 & \frac{1}{\sqrt{2}} & 0 & \frac{1}{\sqrt{2}}\\
0 & \frac{1}{\sqrt{2}} & 0 & -\frac{1}{\sqrt{2}}\\
\frac{1}{\sqrt{2}} & 0 & -\frac{1}{\sqrt{2}} & 0\\
\end{pmatrix}$

My motivation for the question stems from page 5 of physics paper: Information Flow in Entangled Quantum Systems

When studying algorithms whose intended inputs are qubits in unknown
  initial states, it may be convenient to work with other Heisenberg
  states $|\psi\rangle \neq |0,...,0;0\rangle$ but note, nevertheless, that by choosing any
  unitary matrix $U$ with the property $|\psi\rangle = U|0,...,0;0\rangle$, and setting $\hat q_a(0) = U^\dagger(\hat 1^{a-1} \otimes \hat \sigma \otimes \hat 1^{n-a})U$ instead of (5), it is
  always possible to choose the Heisenberg state to be $|0,...,0;0\rangle$.

I can use the unitary matrix to work out what the starting value of each quantum computing observable should be. For example $U^\dagger (\hat 1 \otimes \hat \sigma_z) U$ evaluates to $\hat \sigma_x \otimes \hat \sigma_z$. The physics paper indicates that it wouldn't have mattered which of the range of unitary matrices I had constructed; it states "by choosing any unitary matrix U". I think that if I understood why the choice of unitary matrix does not matter, it would point me to a way to shortcut this process.

答:
Jean Marie's answer already gives a specific process by which to build the matrix $U$ in the context of your question, but I personally gained some insight by rephrasing it in bra/ket notation (both in where the Gram-Schmidt process comes in and how the process can be generalized), so I think the following might be useful for other people finding this question.

We may take that, in the computational basis,

$$\begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} \rightsquigarrow |0^{\otimes 2}\rangle$$

(here I'm using $|0^{\otimes 2}\rangle$ to denote that it's a two-qubit space) and let

$$\begin{pmatrix} 1/\sqrt{2} \\ 0 \\ 0 \\ 1/\sqrt{2} \end{pmatrix} \rightsquigarrow \frac{|00\rangle + |11\rangle}{\sqrt{2}} = |\psi\rangle$$

Then, surely, because our unitary transformation must map every element of the computational basis to some other element of the Hilbert space, and in particular maps $|0^{\otimes 2}\rangle$ to $|\psi\rangle$, it must be of the form

$$\hat U = |\psi\rangle\langle 0^{\otimes 2}| + \sum_{k \neq 0} |u_k\rangle \langle k| $$

where $|u_k\rangle$ is some element of the Hilbert space of two qubits.

Now, we impose the condition of unitarity (recall the completeness relation):

$$ U^\dagger U = I $$
$$ \Leftrightarrow \left (|0^{\otimes 2}\rangle\langle\psi| + \sum_{k\neq 0} |k\rangle\langle u_k| \right)\left (|\psi\rangle\langle0^{\otimes 2}| + \sum_{k'\neq 0} |u_{k'}\rangle\langle k'| \right) = \sum_k |k\rangle\langle k|$$

Which is satisfied if

$$ \langle u_k | \psi \rangle = 0 \; , \qquad \langle u_k | u_{k'} \rangle = \delta_{k,k'}$$

(You may verify this by writing out the product explicitly.)

So that, in fact, $\{|\psi\rangle, |u_k\rangle\}$ (for running $k=1,\ldots,2^2-1$) form an ortho-normal basis.

Therefore, in order to construct $\hat U$, start with set $\{|\psi\rangle\}$ and augment it to an ortho-normal basis set of your two-qubit space via the Gram-Schmidt Process. Then, assign $u_k$ arbitrarily to the elements of the basis that are not $|\psi\rangle$.

The matrix form of the operator can be obtained by calculating

$$ U = \big ( \; \langle i | \hat U | j \rangle \; \big ) $$

for your basis of choice.


问:
Prove the sequence $\frac{1}{a_n}=1+2f(n)-a_{n-1}$ contains every positive rational number exactly once.
For a positive integer denote by $f(n)$ the largest integer $k$ with $2^k | n$. Let $a_0=0$ and consider the sequence given by $\frac{1}{a_n}=1+2f(n)-a_{n-1}$. Prove that this sequence contains every positive rational number exactly once.

I started with the following:

By the inductive hypothesis, assume that there is some set $S$ with the elements $\{a_0, a_1,..., a_n|a\in\mathbb{Q^+}\}$ such that no $a_i = a_j$ for distinct $i,j $ $(0\leq i,j\leq n)$.

Now we need to prove $a_{n+1}$ is a positive rational and not equal to any other element in $S$. At this point I'm having some troubles. It's easy to see that $a_{n+1}$ will always be a rational, but how do you prove that it will always be positive with the $f(n)$. And for the second part of the inductive step, I tried a proof by contradiction, assuming there was some $a_k = a_{n+1}$. I kept hitting dead ends at this point.

答: You prove that $a_{2n+1}>a_{2n}$, which eventually leads to proving $a_{2n}<1$ and $a_{2n+1}>1$. This ultimately solves the positive rationals issue and leads to showing no repetitions exist within the set $S$.


答:
I will just streamline your proof, following your idea: suppose $S$ is open, nonempty and connected. Pick $p\in S$ and let $U$ be the set of points in $S$ that can be
joined to $p$ by a path in $S$  and let $V$ be the complement of $U$. Then $S=U\cup V.$ Note $U$ is nonempty because it contains $p$.

Let $q\in U$ so that there is a path $\gamma$ joining $q$ to $p$. Now let $B$ be any ball in $S$ containing $q.\ B$ is convex so the path $\gamma': t\mapsto (1-t)q'+qt$ joins any point $q'\in B$  to $q.$ So $\gamma'*\gamma$ is then a path that joins $q'$ to $p$. Therefore $q\in B\subseteq U$ and so $U$ is open.

Now take $q\in V.$ Since $q$ cannot be joined to $p$ by a path and since the points from every ball $B$ about $q$ can be joined to $q$ by a path, it follows that any ball in $S$ about $q$ cannot contain points from $U$. This means that $V$ is open.

Then $U$ and $V$ form a separation of $S$, which is a contradiction so $V$ must be empty since $U$ is not.

*Remark: all we used here is convexity of balls in $\mathbb R^n$. The more fundamental condition, is local path-connectedness. We have: locally path-connected+connected = path-connected.

Title: Every open connected set $S \subset \mathbb{R}^n$ is path-connected.

Body:
$\mathbf{Attempt:}$Consider the open cover $\bigcup_{x\in S} B(x,r_x)$    of $S$ with each $B(x,r_x)\subset S$ for some $r_x>0$.

We can invoke the Lindelöf property to get ourselves a countable subcover $\bigcup_{i\in \mathbb{N}} B(x_i,r_{x_i})$    of $\bigcup_{x\in S} B(x,r_x)$ which still covers $S$.
We know that every ball $B(x,r_x)=\{y\in \mathbb{R}^n: d(x,y)<r_x\}\subset S$ is path connected.

$\underline{Claim:}$ The union over a family of non-empty path-connected sets $\{A_i\}_{i\in I_n}$ remains path-connected if for $k =1,2,...,n-1$

$\displaystyle(\bigcup_{i\in I_n\setminus J_k}A_i)\bigcap (\bigcup_{t\in J_k} A_t)\neq \emptyset$

$\forall n \geq 2$, where $I_n=\{1,2,...,n\}$ and $J_k=\{s_1,s_2,...,s_k\}\subset I_n$ where $s_i$ takes arbitrary value and $s_i \neq s_j$ for any two $i\neq j$.

$\underline{Justification:} $
For $n=2$, consider $A_1$ and $A_2$ to be two path connected sets with non-empty intersection. Pick any two $a,b \in A_1 \cup A_2$. For $a,b \in A_1$ or $a, b \in A_2$ we can find readily find a path connecting them within that set.
Now, for $a \in A_1$ and $b\in A_2$ (WLOG), define $h:[0,1] \to A_1\cup A_2$ such that $h(t)=f(2t)$ for $t \in [0,1/2]$ and $h(t)=g(2t-1)$ for $t \in [1/2,1]$ where $f:[0,1] \to A_1$ and $g:[0,1] \to A_2$ such that $f(0)=a$ and $f(1)=c$ and $g(0)=c$ and $g(1)=b$, $c \in A_1\cap A_2$. Clearly, $h$ is continuous on $[0,1]$ with $h(0)=a$ and $h(1)=b$. Hence $A_1 \cup A_2$ is path connected.

Let for $n=m$, $\displaystyle(\bigcup_{i\in I_m\setminus J_k}A_i)\bigcap (\bigcup_{t\in J_k} A_t)\neq \emptyset$.

Put $J_1=1$. Then we get at least one $r_1\neq 1$ such that $A_1\cap A_{r_1}\neq \emptyset$, i.e $A_1 \cup A_{r_1}$ is path connected. Next, let us set $J_2=\{1,r_1\}$. We get $r_2\neq 1, r_1$ with $A_{r_2}\cap(A_1\cup A_{r_1}) \neq \emptyset$. So $A_1\cup A_{r_1}\cup A_{r_2}$ is path connected.

Iterating this process until we exhaust all of $I_m$, we find that $\bigcup_{I_m} A_i$ remains path-connected. This argument holds for $m$, $m+1$ $\cdots$. So for any such countable family, it holds good as well.

Going back to our countable open cover of $S$, we must have $\displaystyle(\bigcup_{i\in \mathbb{N}\setminus J_k}B(x_i,r_{x_i}))\bigcap (\bigcup_{t \in J_k} B(x_t,r_{x_t}))\neq \emptyset$, for all $k\in \mathbb{N}$ and any $J_k$. [Otherwise its emptiness would give us $C=\bigcup_{i\in \mathbb{N}\setminus J_k}B(x_i,r_{x_i})$ and $D=\bigcup_{t\in J_k}B(x_t,r_{x_t})$ for some $J_k$ corresponding to some $k$, such that $C\cap D=\emptyset$ and $C\cup D = S$, both of which are open in the subspace metric on $S$, implying that $S$ is disconnected].

We can now establish the path-connectedness of $S\subset \mathbb{R}^n$ by appealing to our pre-verified claim and choosing $A_i=B(x_i,r_{x_i})$.

$\text{Is this okay? Kindly Verify}.$


问:
Change of variable to show $\int_0^{\infty}\frac{dx}{1+x^2}=2\int_0^1\frac{dx}{1+x^2}$
Which change of variable can be used to show
$$\int_0^{\infty}\frac{dx}{1+x^2}=2\int_0^1\frac{dx}{1+x^2}$$
(direct integration isn't allowed, must use change of variable)

Body:
The required change of variable is
$$x = \tan ( 2\tan^{-1}y),\>\>\>\>\> dx = \sec^2(2\tan^{-1}y)\frac{2dy}{1+y^2}
$$
which leads to
$$\int_0^{\infty}\frac{dx}{1+x^2}
= \int_0^{1}\frac{\sec^2(2\tan^{-1}y)}{1+ \tan^2( 2\tan^{-1}y)}
\frac{2dy}{1+y^2}
=2\int_0^1\frac{dy}{1+y^2}$$


问:
Application of extended Euclidean algorithm
I tried applying the algorithm from Wikipedia in order to calculate $-133^{-1}\mod  256$

I spent already time myself finding the mistake but no success. This is how I did go about applying the algorithm:

r
newr
quotient
t
newt

256
-133
a
0
1

-133
123
-1
1
1

123
-10
-1
1
2

-10
3
-12
2
25

3
-1
-3
25
77

-1
0
-3
77
256

The solution should be $-77$

答:
The loop invariant is $\,-133\, t_k\equiv r_k\pmod{\!256},\,$ so at termination, reading that in the 2nd last row this becomes: $\, -133\cdot 77\equiv -1,\,$ so negating  $\,-133(-77)\equiv 1,$ i.e. $\,(-133)^{-1}\equiv -77$.

The Wikipedia algorithm is working with the system of least nonnegative residues, so you could have avoided the need for negation by working in this system, starting with $\,-133\equiv 123$.

Does this mean I could apply the algorithm for negative numbers if I set t=t∗r at the end?

The  key idea of the algorithm is that $\bmod 256,\,$ given $\,r > r'> 0\,$ both multiples of $-133,\,$ then we can find a smaller multiple $\,r'' := r\bmod r' = r-q\,r'.\,$ Indeed if $\,r \equiv -133t,$ $\,r'\equiv -133t'$ then $\,r'' = r-q\,r' \equiv -133(t-qt')$ remains a multiple of $\,-133$.

The algorithm starts with the two obvious multiples $\,r_0\equiv 0\equiv 256,\,$ and $\,r_1 \equiv -133,\,$ then generates a chain of descending multiples till it reaches $\,0.\,$ The row with the last nonzero $\,r\,$ yields the sought result, as explained in the first paragraph above.

If you use negative residues $\,r_i\,$ then we can achieve descent by ensuring that they have decreasing magnitude, i.e. $\,|r_{k+1}| < |r_k|.\,$ Then the algorithm terminates with the least magnitude multiple $\,r\not\equiv 0\,$ and the gcd is $\,|r|,\,$ and the inverse can be obtained by negating (if need be), as above.

To gain better intuition on this Euclidean descent process (sequence of decreasing multiples) you may find it helpful to view the simpler case of Gauss's algorithm.


问:
How to show a problem is NP-hard
Ok, assume you have an undirected graph of finite size with edges with weight = 1. The graph is sparse. From any given node, there is a path to any other node.

Now, we have two cars somewhere in the graph that are constantly going from one destination to the other. Traversing an edge takes exactly one second. Given any input lists of destinations for both cars, we want to find the quickest routes for both cars. The destinations in the lists should be visited in order by their respective cars.

These are two problems that could individually be solved easily with Dijkstra's algorithm. However, the cars may never collide in the nodes. They may be traversing the same edge at the same time but they may never be in the same node at the same time.

I'm supposed to find the best possible routes for the two cars that result in the lowest overall time using greedy algorithms. What I am doing is to use Dijkstra's algorithm to solve for the two cars individually and then resolve collisions by making the car with the earliest finish time wait.

This is, however, not the most optimal solution. I have been hinted that this problem is NP-hard and I have to either show this or come up with an algorithm that gives the globally optimal solution.

But I'm not sure this problem is actually NP-hard and I get completely lost when trying to prove this. Yes, you have to reduce the problem at hand to a known NP-hard problem but I don't even know where to start!

Can anybody help me out with this?

答:
Here's how you can do it in polynomial time. Say we are given the problem over the graph $G=(V,E)$. We first construct another graph $G' = (V',E')$. The set of nodes $V'$ will simply be $V^2\setminus\{(u,u)|u\in V\}$. The edge relation $E'$ will be such that $E'((u,v),(w,x))$ if and only if $E(u,w)$ and $E(v,x)$ (without loss of generality we assume that all nodes have self loop in $E$, so that waiting can be accounted for in this edge relation). Let $U = \{u_0,u_1,\ldots,u_n\}$ and $W = \{w_0,w_1,\ldots,w_m\}$ be the destination lists for the cars, where $u_0$ and $w_0$ are the starting positions of the cars. We now create a copy of $G'$ for each $u_i,w_j$, which we denote $G_{i,j}$ (and the copy of a node $v \in V'$ is denoted by $(v,i,j)$). We put all graphs $G_{i,j}$ into a single graph $H$ in the following way. Let $i,j$ be arbitrary. Then we add the edges $((u_{i-1},v,i-1,j),(u_{i-1},v,i,j))$, $((v,w_{j-1},i,j-1),(v,w_{j-1},i,j))$ for all $v\in V$, and the edge $((u_{i-1},w_{j-1},i-1,j-1),(u_{i-1},w_{j-1},i,j))$. We give each of these new edges weight zero, so that traversing them costs no time.

Then we just run Djikstra's on $H$ with source $(u_0,w_0,0,0)$ and target $(u_n,w_m,n,m)$. The running time of this will be $O([(|V|^2 + |E^2|)nm]^3)$, which is clearly polynomial. This is actually just a dynamic programming algorithm.

Title: How to show a problem is NP-hard


问:
How did this binomial $(x^2+3)^{-\frac 13}-\frac 23x^2(x^2+3)^{-\frac 43}$ get factored into these $(x^2+3)^{-\frac 43}(\frac 13x^2+3)$ factors?
This is an exercice in PRECALCULUS mathematics for calculus 7th, Section 1.3 Question 129.
And I just can't figure out how the book came up whith the answer.

I know how to factor this binomial:
$$(x^2+3)^{-\frac 13}-\frac 23x^2(x^2+3)^{-\frac 43}$$
... into these factors (it may be wrong):
$$(x^2+3)^{-\frac 43}  ((x^2+3)^{\frac 23}-\frac 23x^2)$$

But from there i have no idea how to continue, I'm following the basic strategy
of "pulling out" the smallest shared term $(x^2+3)^{-\frac 43}$

答: HINT: As $-\frac{1}{3}=-\frac{4}{3} +1$, it follows that $(x^2+3)^{-\frac{1}{3}} = (x^2+3)^{-\frac{4}{3}}(x^2+3)$. In other words as noted in the comments already, your exponent of $\frac{2}{3}$ should be replaced by 1 as the exponent. Then continue as you would have before...


问:
A theoretical model of a flow network.
I believe I've got a correct understanding of how flow network works.

Yet, I've bumped into a theoretical question that I'm not even sure if interpreted right. Here it is:

Provide an example of a network with n nodes and with integer
capacities such that there is an exponential (i.e. greater than $c^n$
for some constant $c \gt 1$) number of different integer maximal flows
in it. Two flows are considered different if they differ on at least
one arc of the network

Unfortunately, I cannot post picture of a graph that I've constructed (due to the lack of 10 reputation), so I'll describe it formally

$V = \lbrace S, 1, 2, 3, T\rbrace$
$C(S,1) = s1$

$C(S,2) = s2$

$C(S,3) = s3$

$C(T,1) = t1$

$C(T,2) = t2$

$C(T,3) = t3$

$C(1,2) = ?$

$C(S,1) = ?$

So, one thing that I understood about that excercise, is that in order to have sufficient input flow and output capacity $$t1 + t2 + t3 \ge c^n \le s1 + s2 + s3$$

But what about $C(1,2)$ and $C(2,3)$? Maybe I've got totally wrong idea about question itself?

It would be a huge help even to paraphrase the task, as I think I'm reading it wrong.

答:
Since you want to have exponentially many maximal flows, one way to construct it is to give many choice at first then to make a bottleneck.

As the original question asked to construct a graph for an arbitrary $n$, we will give a whole family of graphs $(G_n)_n$ with $G_n$ having (roughly) $n$ vertices and around $2^n$ different maximal flows(the graphs will actually have $n+1$ vertices plus the source and the sink, but it doesn't matter for the asymptotic):

Le $G_n$ be  the following graph :

its quite clear that a maximal flow has a capacity of $n \over 2$, now, one as to chose which vertices $a_i$ to visit for the flow. Clearly there is $\binom{n}{n/2}$ possible choice, meaning that there are $\binom{n}{n/2}$ different maximal flows. The asymptotics of this number is $2^n$ (see limit of $2n$-th root of $2n$-th central binomial coefficient -- $\lim_{n\to \infty}{2n \choose n}^{\frac{1}{2n}}$ for instance)

You can get more precise estimate on the number of flows but I hope this is more or less what you've asked.

[EDIT]
rethinking about it, this construction is a bit of an overkill as we can find an answer that does not involve knowing the asymptotic of the binomial coefficient (we'll end up with a smaller constant $c$ though).

the following graph

has graph with $8=2\times 4$ vertices and $4=2^2$ maximal flows.

Using three times this diamond  shaped graph we end up with :
<img src="https://i.stack.imgur.com/gnlqu.png" alt="graph with $3\times 4$ vertices and $2^3$ maximal flows" />
which has  $12=3\times 4$ vertices and $8=2^3$ maximal flows

Repeating $k$ times this diamond shaped graph give a graph  with $4k$ vertices and $2^k$ maximal flows, so $n= 4k$ vertices and  $2^{n/4} = (2^{1/4})^n$ maximal flows.

Title: A theoretical model of a flow network.


Title: How did this binomial $(x^2+3)^{-\frac 13}-\frac 23x^2(x^2+3)^{-\frac 43}$ get factored into these $(x^2+3)^{-\frac 43}(\frac 13x^2+3)$ factors?

Body:
This is an exercice in PRECALCULUS mathematics for calculus 7th, Section 1.3 Question 129.
And I just can't figure out how the book came up whith the answer.

I know how to factor this binomial:
$$(x^2+3)^{-\frac 13}-\frac 23x^2(x^2+3)^{-\frac 43}$$
... into these factors (it may be wrong):
$$(x^2+3)^{-\frac 43}  ((x^2+3)^{\frac 23}-\frac 23x^2)$$

But from there i have no idea how to continue, I'm following the basic strategy
of "pulling out" the smallest shared term $(x^2+3)^{-\frac 43}$

Body:
Since
$$
(x^2+3)^{-\frac{1}{3}} = (x^2+3)^{-\frac{4}{3}}(x^2+3)
$$
The original one becomes
$$
(x^2+3)^{-\frac 13}-\frac 23x^2(x^2+3)^{-\frac 43}=  (x^2+3)^{-\frac{4}{3}}(x^2+3)-\frac 23x^2(x^2+3)^{-\frac 43}\\= (x^2+3)^{-\frac{4}{3}}\left (\dfrac 13x^2+3\right )
$$
We are done.


问:
Looking for a proof of two combinatorial summation identities
While working on a problem I came across the following similar combinatorial identities valid by numerical evidence $(n\ge m)$:
$$\begin{align}
A(n,m)&\equiv\sum_{k\ge1}\binom km\binom{n-1}{k-1}=2^{n-m-1}\binom nm\frac{n+m}{n},\\
B(n,m)&\equiv\sum_{k\ge1}\left[\binom{\left\lfloor\frac k2\right\rfloor}m
+\binom{\left\lceil\frac k2\right\rceil}m\right]\binom{n-1}{k-1}=2^{n-2m}\binom {n-m}{m-1}\frac{n+1}{m}.
\end{align}$$

I am looking for an algebraic proof of these identities.

Is there a smart way to prove:
$$
B(n,m)=A(n-m+1,m)
$$
without explicit evaluation of the sums?

答:
Using a coefficient extractor Eg
\begin{eqnarray*}
\binom{k}{m} = [x^m]:(1+x)^k.
\end{eqnarray*}
We have
\begin{eqnarray*}
\sum_{k\ge1}\binom km\binom{n-1}{k-1} &=& [x^m]: \sum_{k=1}^{n} \binom{n-1}{k-1} (1+x)^k \\
&=& [x^m]:  (1+x) (2+x)^{n-1} \\
&=& 2^{n-1-m} \binom{n-1}{m} +2^{n-m} \binom{n-1}{m-1} \\
&=& 2^{n-1-m}\left( \binom{n-1}{m} +2 \binom{n-1}{m-1} \right)\\
&=& 2^{n-1-m} \frac{(n-1)!}{m!(n-m)!} \left( n-m+2m \right)\\
&=& 2^{n-1-m} \frac{(n-1)!}{m!(n-m)!} (n+m).\\
\end{eqnarray*}
Which is the first identity (upto a factor of $n$).


问:
Integer Linear Programming Conditional Constraints
How can I create a constraint that reflects the following: if $x_{ij} = 1$ AND $x_{jk} = 1$ THEN $x_{ik} = 1$?

All my variables $x_{ij}$ are binary. To provide some context:

I'm trying to create a linear equation system to be solved via the simplex algorithm that provides a solution to the problems schools face when creating class groups. Each student chooses 5 other students that he would like to be with in the following year. The school promises that each student will be in a class with at least one of the students they chose. To create the equation system I decided that my variables will be boolean and represent the following: $x_{ij} = 1$ if student $i$ is with student $j$ and $x_{ij} = 0$ otherwise. Thus, $x_{ij}= x_{ji}$ and $x_{ii} = 1$.

However, I'm having trouble with the following constraint: if student $i$ is together with student $j$ and student $j$ is together with student $k$, then inevitably student $i$ will be together with student $k$. This is represented by the constraint I mentioned at the beginning of the question.

I tried using the big M approach as mentioned in other questions but to no avail. In these questions there was only one condition but I have two.

Even if I solve this problem, how can this be scalable? For example: if $x_{12} = x_{23} = x_{14} = 1$ then $x_{13} = x_{34} = x_{24} = 1$. Maybe the variables I chose are not correct and I'm overcomplicating things. If this is the case, any guidance in the right direction would be more than welcomed.

Thanks for the help in advance!

答:
To try to answer the question I asked in the last paragraph and complement Jean Marie's very precise and helpful answer:

Let's continue with the example I put in my question: if $x_{12} = x_{23} = x_{14} = 1$  then $x_{13} = x_{34} = x_{24} = 1$.

Using the constraint $x_{ij} + x_{jk} - x_{ik} <= 1$ we have that:

$x_{13} = 1$

Moreover, as $x_{ij} = x_{ji}$: given $x_{12} = x_{14} = 1$, then $x_{24} = 1$

Finally, as we have that $x_{13} = 1$ and $x_{14} = 1$, then $x_{34} = 1$.

I know this is just an example and it does not prove anything, so if anyone finds proof to support that the constraint $x_{ij} + x_{jk} - x_{ik} <= 1$ is enough to represent all of the transitivity possibilities I would very much appreciate they post it as an answer.


问:
What is the sum of the all possible $6$ digits numbers which are chosen in the set of {$0,0,0,1,2,3,4,5,6,7,8$}
When i get around in park , i thought about combinatorics and made up a question in my mind.

However, i cannot be sure about my solution because as you know , it is very easy to miss some details in combinatorics.So , i want to be checked my solution here.

Question: What is the sum of the all possible $6$ digits numbers which are chosen in the set of {$0,0,0,1,2,3,4,5,6,7,8$}

My humble attempt:

First step-) We can put $1$ element in the first digit in the set of {$1,2,3,4,5,6,7,8$},so there left $7+3=10$ possible numbers to put into the other $5$ digits. We can calculate it by $\frac{10 \times9\times8\times7\times6}{3!}=5040$ (we made division because of the zeros)

$\therefore 5040\times(1+2+3+4+5+6+7+8=36)\times10^5$

Second Step-) We have chosen one element for the first digit which is not zero.Then, for the second digit:

$1\times(\frac{7\times9\times8\times7\times6}{3!}=3528)\times10^4$

This will continue up to the sixth digits in the same logic.

Then $5040\times10^5+3528\times10^4+3528\times10^3+3528\times10^2+3528\times10^1+3528\times10^0=543199608$

Is my solution correct ? If not, can you write the correct solution.

Moreover , even if it is corect if you know much shorter way, can you share with us ?

Have a nice day...

答:
I believe your approach to the question is correct, however, there seems to be one mistake. In your solution you claim that there are $\frac{10 \cdot 9 \cdot 8 \cdot 7 \cdot 6}{3!} = 5040$ numbers with a particular starting digit. However, this is not quite correct. To illustrate your mistake here is a simpler example:

A simpler example

Let us say that we have the digits $\{0,0,1,2,3,4\}$ and we want to find all of the numbers of length 4 that start with $1$. Then we can list them all out to find that there are $33$ of them:

$1234, 1243, 1324, 1342, 1423, 1432$

$1023, 1024, 1032, 1034, 1042, 1043, 1203, 1204, 1230, 1240, 1302, 1304, 1320, 1340, 1402, 1403, 1420, 1430$

$1002, 1003, 1004, 1020, 1030, 1040, 1200, 1300, 1400$

How the total number is calculated is perhaps hinted by the way I have arranged the numbers above. Namely, we want to calculate in how many ways we can get a number of length $4$ starting with $1$ such that none of the zeros are used, one of the zeros is used, or all of the zeros are used.

If no zero gets used we get  $ \binom{3}{0} \cdot 3 \cdot 2 \cdot 1 = 6$ results.

If one zero gets used we get $ \binom{3}{1} \cdot 3 \cdot 2 = 18 $ results.

If two zeros get used we get $ \binom{3}{2} \cdot 3 = 9$ results.

The sum of these yields exactly $33$. However, if I understood your calculation correctly, you would have claimed that there are $\frac{5 \cdot 4 \cdot 3}{2!} = 30$ results which is incorrect.

Back to the original problem

Now coming back to the original problem let us apply the same procedure. Consider any number $XZZZZZ$ where $X$ is fixed and each $Z$ represents an arbitrary digit.

If no zero gets used we get  $ \binom{5}{0} \cdot \frac{7!}{2!}  = 2520 $ results.

If one zero gets used we get $ \binom{5}{1} \cdot \frac{7!}{3!} = 4200$ results.

If two zeros get used we get $ \binom{5}{2} \cdot \frac{7!}{4!} = 2100$ results.

If three zeros get used we get $ \binom{5}{3} \cdot \frac{7!}{5!} =  420 $ results.

So in total there are $9240$ numbers where $X$ is the first digit.

Now note that an integer contributes nothing to the sum if it is $0$ and fix the first two digits so that our number is given by $XYZZZZ$. We then ask ourselves how many numbers of this kind we can make. This is simply a slight alteration of what we did before.

If no zero gets used we get  $ \binom{4}{0} \cdot \frac{6!}{2!}  = 360 $ results.

If one zero gets used we get $ \binom{4}{1} \cdot \frac{6!}{3!} = 480$ results.

If two zeros get used we get $ \binom{4}{2} \cdot \frac{6!}{4!} = 180$ results.

If three zeros get used we get $ \binom{4}{3} \cdot \frac{6!}{5!} =  24 $ results.

Now allowing $Y$ to be any non-zero value we see that there are $1044 \cdot 7  = 7308$ numbers which start with $X$ and have a non-zero second coefficient.

Since the same procedure can be applied to the number $XZZZZZ$ where any $Z$ is replaced by a $Y$, we conclude that our answer is:

$$36 \cdot \left( 9240 \cdot 10^5 + 7308 \cdot 11111 \right)$$

A general solution

By now, you might be able to see how we can construct the general solution to this problem. If we have an input of consisting of $m$ zeros, the first $n$ positive integers and you are creating a number of length $r$ with $m \leq r-2$ and $n \geq r$ then I believe the general solution to this problem is given by:

$$ \frac{(n)(n+1)}{2} \cdot
\left(
10^{r-1}\sum_{i=0}^m \left[\binom{r-1}{i} \cdot \frac{(n-1)!}{(n-r+i)!} \right]
+ \left(\sum_{i=0}^{r-2} 10^i\right)
\sum_{i=0}^m\left[\binom{r-2}{i} \cdot \frac{(n-1)!}{(n-r+i)!} \right]
\right)
$$

Comment

Combinatorics is not my strong suit by any stretch of the imagination, so by all means, please point out anything you think is incorrect or is explained poorly.


问:
exact meaning of uniform integrability for empirical distributions
Suppose we have $n$ non-negative integer-valued random variables $X_1,\ldots,X_n$ and consider the empirical distribution $$Q := \frac{1}{n}\sum_{i=1}^n \delta_{X_i}.$$ We equip any probability mass function $q \in \mathcal{P}(\mathbb{Z}_+)$ with the usual $\ell^1$ norm $\|q\|:= \sum_{k=0}^\infty q_k$. I am confused on the precise meaning of the statement that the empirical distribution $Q$ is uniformly integrable (notice that $Q$ depends on $n$). In the typical setting, we say that a collection of random variables $(X_n~\colon n \in \mathbb N)$ is U.I. (Uniformly Integrable) if there exists some $K >0$ so that $\sup_{n\in \mathbb N} \mathbb{E}(|X_n|\mathbf{1}_{|X_n| \geq K}) < \epsilon$ for each pre-fixed $\epsilon > 0$. But how does this general definition translates into the aforementioned setting really bothers me... Thanks for any help!

答:
I'm going to reference arxiv.org/pdf/1804.04608.pdf, which was cited in the comments as the motivation for this question. The paper uses the following notation:

$\Omega = \{(\eta_i)_{i=1,\dots,n}\in \mathbb{Z}_+: \sum_{i=1}^n \eta_i = m\}$. Because we vary $m$ and $n$, I'm going to instead write $m_n$ and $\Omega^m_n$. The paper seems to be implying that $(\eta_i)_{i\in\mathbb{N}}$ is some fixed sequence.

$Q(0) = \frac{1}{n}\sum_{i=1}^n \delta_{\eta_i}$ is the empirical measure. Again, I will write $Q_n = \frac{1}{n}\sum_{i=1}^n \delta_{\eta_i}$ for clarity, omitting the $(0)$ as this question does not regard the dynamics of the process introduced in the paper. For each $n$, we regard $Q_n$ as an element of $\ell^1(\mathbb{Z}_+)$.

$Q_n \to q$ in $\ell^1(\mathbb{Z}_+)$, $\frac{m_n}{n} \to \rho$ and $\lambda = \sum_{k=0}^\infty kq_k$.

We ignore the dynamics introduced in the paper. We can clearly see that each $Q_n$ is a probability measure (I'm assuming the configuration $(\eta_i)_{i\in\mathbb{N}}$ is fixed and non-random. If I misread that, then the argument only changes slightly). Furthermore, convergence in $\ell^1$ is equivalent to total variation convergence, so $q$ is also a probability measure. So, we can assign to each $n$ a random variable $Y_n := \eta_{U_n}$ where $U_n$ is sampled from $\{1,\dots,n\}$ uniformly at random. Then $Y_n$ has distribution $Q_n$. Let $Y$ be some random variable sampled from $q$. Then $Y_n \to Y$ in total variation. For each $n$, $\mathbb{E}[Y_n] = \frac{1}{n}\sum_{i=1}^n \eta_i = \frac{m_n}{n} \to \rho$, and $\mathbb{E}[Y] = \sum_{k=1}^\infty kq_k = \lambda$.

The paper states that $\rho = \lambda$ if $Q(0)$ is uniformly integrable. What they mean is that if the sequence of random variables $\{Y_n\}_{n \in \mathbb{N}}$ is uniformly integrable, then total variation convergence implies convergence in expectation so that,

$$\rho = \lim_{n\to\infty} \frac{m_n}{n} = \lim_{n\to\infty}\mathbb{E}[Y_n] = \mathbb{E}[Y] = \lambda.$$

The precise definition of this uniform integrability is,

$$\lim_{K\to\infty} \sup_{n \in \mathbb{N}} \mathbb{E}[Y_n\mathbb{I}_{Y_n > K}] = \lim_{K\to\infty} \sup_n \frac{1}{n}\sum_{i=1}^n \eta_i\mathbb{I}_{\eta_i > K} = 0.$$

I tried to come up with a nice counterexample, but I can't think of one where $Q_n$ are not uniformly integrable and it converges to a measure $q$ in total variation. I'd be interested to see if anyone has such a counter example. I suspect that for most if not all counterexamples, $\rho = \infty$ and $\lambda < \infty$.


问:
Inequality $\frac{a}{a^2+1}+\frac{b}{b^2+1}+\frac{c}{c^2+1} \leq \frac{9}{10}$
Prove that if $a,b,c \geq -\frac34$ and $a+b+c=1$ then inequality $\frac{a}{a^2+1}+\frac{b}{b^2+1}+\frac{c}{c^2+1} \leq \frac{9}{10}$ holds.

I've been struggling for proving this inequality for quite long time, could you please give me some hints?

Body:
For all $x \geqslant -\frac{3}{4},$ we have
$$\frac{x}{x^2+1} \leqslant \frac{18}{25} \cdot x+\frac{3}{50}\Leftrightarrow  \frac{(4x+3)(3x-1)^2}{50(x^2+1)} \geqslant 0 \quad (\text{true}).$$
Therefore
$$\frac{a}{a^2+1}+\frac{b}{b^2+1}+\frac{c}{c^2+1} \leqslant \frac{18}{25}(a+b+c)+ 3 \cdot \frac{3}{50} = \frac{9}{10}.$$


问:
$0$-th moment of product of gaussian and sinc function
I would like to calculate the following integrals:

$$\int_{-\infty}^{+\infty} \quad \left(\frac{\sin(\pi a x)}{\pi ax}\right)^2\quad \exp(-bx^2)\,dx$$

$$\int_{-\infty}^{+\infty} \quad \left(\frac{\sin(\pi a x\pm\pi)}{\pi ax\pm\pi}\right)^2\quad \exp(-bx^2) \,dx$$

Thanks!

答:
I have got the following answers with help of Wolfram Mathematica 8.0:

$\int_{-\infty}^{\infty} \left(\frac{sin(\pi a x)}{\pi a x}\right) e^{-b x^2} dx = \frac1{a^2 \cdot \pi^\frac{3}{2}} \cdot \left( -\sqrt{b} + \sqrt{b} \cdot e^{-\frac{a^2 \cdot \pi^2}{b}} + a \cdot \pi^\frac{3}{2} \cdot \operatorname{Erf}\left( \frac{\pi a}{\sqrt{b }} \right) \right)$ only if $\operatorname{Re}(b) > 0$ and $a \ge 0$, where $\operatorname{Erf}(x) = \frac{2}{\sqrt{\pi}} \cdot \int_0^x e^{-t^2} dt$

Unfortunately, Mathematica falls to evaluate the integral $\int_{-\infty}^{\infty} \left(\frac{sin(\pi a x)}{\pi a x + \pi}\right)^2 e^{-b x^2} dx$

Hope, it helps.


答:
You can obtain the constraint via conjunctive normal form as follows:
$$
(x_{i,j} \land x_{j,k}) \implies x_{i,k} \\
\lnot (x_{i,j} \land x_{j,k}) \lor x_{i,k} \\
\lnot x_{i,j} \lor \lnot x_{j,k} \lor x_{i,k} \\
(1- x_{i,j}) + (1- x_{j,k}) + x_{i,k} \ge 1 \\
x_{i,j} + x_{j,k} - x_{i,k} \le 1
$$
You need only enforce these constraints for $i < j < k$.

Title: Integer Linear Programming Conditional Constraints

Body:
How can I create a constraint that reflects the following: if $x_{ij} = 1$ AND $x_{jk} = 1$ THEN $x_{ik} = 1$?

All my variables $x_{ij}$ are binary. To provide some context:

I'm trying to create a linear equation system to be solved via the simplex algorithm that provides a solution to the problems schools face when creating class groups. Each student chooses 5 other students that he would like to be with in the following year. The school promises that each student will be in a class with at least one of the students they chose. To create the equation system I decided that my variables will be boolean and represent the following: $x_{ij} = 1$ if student $i$ is with student $j$ and $x_{ij} = 0$ otherwise. Thus, $x_{ij}= x_{ji}$ and $x_{ii} = 1$.

However, I'm having trouble with the following constraint: if student $i$ is together with student $j$ and student $j$ is together with student $k$, then inevitably student $i$ will be together with student $k$. This is represented by the constraint I mentioned at the beginning of the question.

I tried using the big M approach as mentioned in other questions but to no avail. In these questions there was only one condition but I have two.

Even if I solve this problem, how can this be scalable? For example: if $x_{12} = x_{23} = x_{14} = 1$ then $x_{13} = x_{34} = x_{24} = 1$. Maybe the variables I chose are not correct and I'm overcomplicating things. If this is the case, any guidance in the right direction would be more than welcomed.

Thanks for the help in advance!


问:
Semigroup without a weak basis
Let $\mathfrak{S}=(S,*)$ be a semigroup and $X\subseteq S$. Consider the functional closure $\overline{X}$, i.e. minimal set containing $X$ and closed under $*$. Let's say that $X$ is a weak basis (in contrast with the basis that is defined for a stronger concept of the algebraic closure) if $\overline{X}=S$ and $\forall(x\in X):x\notin \overline{X-\{x\}}$. One may prove that finite semigroups, free monoids and groups contain weak bases. Does it hold for all semigroups? If not, are there some counterexamples?

答: As it was shown in the comments, the assertion actually isn't true for groups and the counterexample is $(\mathbb{Q},+)$. Indeed, assume $a,b$ are elements of the basis $X$ and $a<b$. Suppose $a=x/z$ and $b=y/z$ where $x,y,z\in\mathbb{Z}$ and $z>0$. We can write $1/z=x_1+...+x_n$ where $x_1,...,x_n\in X-\{b\}$. Then $a+(y-x)(x_1+...+x_n)=b$ that gives us a contradiction with the independence of $X$. Thus, $X$ contains just one element $q$. We have $q\neq0$ and thus $0\notin\overline{X}$.

Title: Semigroup without a weak basis