问:
prove $\ e^{n^2} \ge n^n $ for every n by induction
Prove for any $\ n \ge 1 $

$$\ e^{n^2} \ge n^n $$

my attempt:

true for $\ n = 1 $ then for $\ n+ 1 $ :

$\ e^{(n+1)^2} = e^{n^2 + 2n + 1} = e^{n^2} \cdot e^{2n} \cdot e $

$\ ( n+1)^{n+1} = (n+1)^n\cdot (n+1) \le (n+n)^n\cdot(n+1) = (2n)^n \cdot(n+1) = 2^n \cdot n^n \cdot(n+1) \le 2^n \cdot e^{n^2} \cdot(n+1)  $

from here it's obvious $\ e^{2n} \ge 2^n $ but I can't find a way to get rid of $\ n+1 $ and $\ e $?

答:
hint

Taking the $n^{\text{th}} $ root, it is much easier to prove that
$$(\forall n\ge 1)\; e^n\ge n$$

Let $ n\ge 1$ such that $ e^n\ge n.$

$$e^n\ge n\implies e^{n+1}\ge en$$
$$\implies e^{n+1}\ge 2n$$

$$\implies e^{n+1}\ge n+n$$
$$\implies e^{n+1}\ge n+1$$


答:
Cantor's inequality $2^n > n$ implies $e^n > 2^n > n$ for any $n$.

Then just raise it to $n$-th power.

ContentLicense: CC BY-SA 4.0

Title: prove $\ e^{n^2} \ge n^n $ for every n by induction

Body:
Prove for any $\ n \ge 1 $

$$\ e^{n^2} \ge n^n $$

my attempt:

true for $\ n = 1 $ then for $\ n+ 1 $ :

$\ e^{(n+1)^2} = e^{n^2 + 2n + 1} = e^{n^2} \cdot e^{2n} \cdot e $

$\ ( n+1)^{n+1} = (n+1)^n\cdot (n+1) \le (n+n)^n\cdot(n+1) = (2n)^n \cdot(n+1) = 2^n \cdot n^n \cdot(n+1) \le 2^n \cdot e^{n^2} \cdot(n+1)  $

from here it's obvious $\ e^{2n} \ge 2^n $ but I can't find a way to get rid of $\ n+1 $ and $\ e $?


问:
Project Euler problem #731
In this Poject Euler probelm < https://projecteuler.net/problem=731 > I'm asked to find the 10 decimal digits from the nth number onward in the decimal expansion of the infinte serie : $$\sum_{k=1}^\infty\frac1{10^{3^k}3^k}$$  which is equal to the stoneham number $\alpha_{10,3}$

My try was : take i such that $3^i$ > n then take all the fractions of the form $$a_k=\frac1{3^k}$$ such that k in [1..(i-1)] .

Then for all the fractions : take the the 10 decimal digits from the nth digit onward and sum them up

This method works fine for A(100) , but it is clear that for large n , this method will not work due to carries addition issue . For example for n=$10^{16}$: we have to sum the 10 decimal digits from the $10^{16}$th number onward of those fractions :  $$a_k=\frac1{3^k}$$   such that k in [1..33] . Is there another method to attack this problem ?

Python code for the case n = 100 :

```<code>a='3' # repeating decimal of 1/3

a*=200

b='1' # repeating deciaml of 1/9

b*=200

c='037' # repeating deciaml of 1/27

c*=200

d='012345679' repeating decimal of 1/81

d*=120

for k in range(99,99+10):

     print(int(a[k])+int(b[k])+int(c[k])+int(d[k]))
</code>```

Stop at $\frac1{81}$ because $10^{243}$ in the denominator will gives us 243 zeros after the decimal point

答:
Hint: Let $i$ be the smallest integer for which $3^i > n$. What we are after are the $10$ digits from the $n$th number onward in the finite sum
$$
S_1 = \sum_{k=1}^i \frac{1}{10^{3^k}3^k}.
$$
Equivalently, we want the first 10 digits after the decimal point in the number $10^{n-1}S_1$, which is equal to
$$
S_2 = \sum_{k=1}^i \frac{10^{n - 3^k - 1}}{3^k}.
$$
That is, we only want the fractional part of $S_2$ expanded to $10$ digits.

Here's code that implements the idea I had in mind:

```<code>import math

n = 10**8

m = int(math.log(n,3))
tot = 0
for k in range(1,m+1):
    phi = 2*3**(k-1)
    exp = n - 3**k - 1
    exp %= phi
    num = 10**exp
    num %= 3**k
    tot += num/3**k
tot -= int(tot)
print(int(tot*10**10))
</code>```

Although it technically works, this method is problematic because $10^{n - 3^k - 1}$ is very large. Instead, we can efficiently compute $10^{n - 3^k - 1} \bmod 3^k$. For instance:

```<code>import math

# SET VALUE OF n HERE
n = 10**8

m = int(math.log(n,3))
tot = 0
for k in range(1,m+1):
    den = 3**k
    exp = n - den - 1
    num = pow(10,exp,den)
    tot += num/den       # python 2: tot += float(num)/den
tot -= int(tot)
print(int(tot*10**10))
</code>```

Title: Project Euler problem #731

Body:
Hint: Let $i$ be the smallest integer for which $3^i > n$. What we are after are the $10$ digits from the $n$th number onward in the finite sum
$$
S_1 = \sum_{k=1}^i \frac{1}{10^{3^k}3^k}.
$$
Equivalently, we want the first 10 digits after the decimal point in the number $10^{n-1}S_1$, which is equal to
$$
S_2 = \sum_{k=1}^i \frac{10^{n - 3^k - 1}}{3^k}.
$$
That is, we only want the fractional part of $S_2$ expanded to $10$ digits.

Here's code that implements the idea I had in mind:

import math

n = 10**8

m = int(math.log(n,3))
tot = 0
for k in range(1,m+1):
    phi = 2*3**(k-1)
    exp = n - 3**k - 1
    exp %= phi
    num = 10**exp
    num %= 3**k
    tot += num/3**k
tot -= int(tot)
print(int(tot*10**10))

Although it technically works, this method is problematic because $10^{n - 3^k - 1}$ is very large. Instead, we can efficiently compute $10^{n - 3^k - 1} \bmod 3^k$. For instance:

import math

# SET VALUE OF n HERE
n = 10**8

m = int(math.log(n,3))
tot = 0
for k in range(1,m+1):
    den = 3**k
    exp = n - den - 1
    num = pow(10,exp,den)
    tot += num/den       # python 2: tot += float(num)/den
tot -= int(tot)
print(int(tot*10**10))


问:
In $A = QR$ factorization do we need basis vectors from the left null space?
I am looking at the factorization $A = QR$ where $A \in \mathbb{R^{m\times n}}$ and $Q$ is orthogonal.

Background

The presentation of QR factorization that I've seen goes as follows. To construct $Q$, first find an orthonormal basis for the column space of $A$. These vectors $\{q_1,...,q_r\}$ will comprise the first $r = \text{rank}(A)$ columns of Q. We then complete the columns of $Q$ by taking orthonormal basis vectors from the left null space $N(A^T)$, and since $C(A)^\perp = N(A^T)$, we know the columns of Q will be orthonormal.

Question

My question is, how do I know that there will be enough basis vectors in $N(A^T)$ to complete the columns of $Q$? Also, is it necessary to take basis vectors from $N(A^T)$, or just convenient since they are guaranteed orthogonal?

答:
First, we are working in reals.  Note that $QR$ factorization is unique when $A$ is invertible (with the convention/requirement that $r_{i,i}\gt 0$), and not unique otherwise.  There are 2 basic approaches for QR factorization in your case.  You've indicated that you want $Q$ to be square.

1.) Run Gram Schmidt on the columns of $A$.  This does not naturally result in $Q$ being square though you can extend to a basis to get there.

2.) Reduce $A$ to (not necessarily square) upper triangular form by repeated application of $Q^{(j)}...Q^{(2)}Q^{(1)}$ where $Q^{(k)}$ is some particularly simple kind of orthogonal matrix -- typically Householder or perhaps Givens.  This naturally results in a case where $Q$ is square.

It sounds like you are doing (1) though its worth your while to learn (2).

Focus on the case where $A$ is tall and skinny. Run Gram Schmidt on the columns of $A$ and if the result is non-zero for $\mathbf a_k$ then append on the right to the matrix $Q$ you are creating.  (If the result is zero ignore it).  Suppose $\text{rank}\big(A\big) = r$.  After completing this you have

$A=QR =\bigg[\begin{array}{c|c|c|c} \mathbf q_1 & \mathbf q_2 &\cdots & \mathbf q_{r}\end{array}\bigg]R$

Note that this is 'thin' QR factorization, and $Q^TQ = I_r$ but $Q$ is not square.

Since you want $Q$ to be square, there is a second step.  Append $m-r$ orthonormal columns to $Q$ to get

$A=Q'R' =\bigg[\begin{array}{c|c|c|c|c|c} \mathbf q_1 & \mathbf q_2 &\cdots & \mathbf q_{r}&\mathbf q_{r+1}&\cdots&\mathbf q_m\end{array}\bigg]\begin{bmatrix} R \\\mathbf  0\end{bmatrix}$

where $Q'$ is augmented to include those extra orthonormal columns and $R'$ is $R$ with rows of zeros appended so that the dimensions line up for matrix multiplication.  If you write this out in terms of the 'outer product' form of matrix multiplication you can confirm these two different factorizations are both equal to $A$.

As for your specific questions

these boil down to, where does $\bigg[\begin{array}{c|c|c|c}\mathbf q_{r+1}&\cdots&\mathbf q_m\end{array}\bigg]$

(which has rank $m-r$)  come from?

if you want to use the left nullspace of $A$, then applying rank nullity and equivalence of row and column rank

$m =\text{rank}\Big(A^T\Big) + \dim\ker \Big(A^T\Big) = \text{rank}\Big(A\Big) + \dim\ker \Big(A^T\Big) =r+ \dim\ker \Big(A^T\Big)$

$\implies \dim\ker \Big(A^T\Big) = m-r $

so yes the left nullspace of $A$ has $m-r$ linearly independent vectors in it -- run gram schmidt on them.  These vectors are already orthogonal to the columns of $A$ or anything generated solely by linear combinations of the columns of $A$ (in particular the columns of thin $Q$).

Is it necessary to use the left nullspace of $A$?

No.  Another approach is to use a random number generator and generate $m-r$ column vectors each having $m$ components that are uniform in $[-1,1]$.  With probability 1 these are linearly independent from the columns of $A$.  So e.g. consider $A'$ to be $A$ with these randomly generated vectors appended on the right.  Now run $QR$ factorization.  Finally delete the last $m-r$ columns in $R$.

(in the real world randomized algorithms are quite useful though you'd use a pseudo random number generator and the set of randomly generated vectors would be linearly independent with probability extremely close to but not quite 1.)

Of course you can also bypass all of this by using approach (2).


答: You can continue your work by taking $\ln$ of both sides and we have $2n+1 \geq n\ln2 + \ln(n+1) \geq n/2 + n+1=3n/2 + 1$. Then we get that $n/2 \geq 0$ with reversible steps.


问:
Counting the numbers between $1$ and $1,000,000$ whose digits sum to $30$

What's the number of numbers between $1$ and $1,000,000$ whose digits sum is $30$?

So I thought of this as a stars and sticks problem, so in the case you have $35\choose 5$ numbers whose sum is $30$. But obviously this number of numbers includes many overlaps (if for instance the requested sum was $8$, then $80=800=8000=134=143=431$ etc.). How do I get rid of the overlaps (inclusion-exclusion)?

Thanks in advance for any assistance!

答: HINT: Can you find the number of integer soloutions of the equation $$x_1+x_2+x_3+x_4+x_5+x_6=30$$ such that  $0\leq x_i\leq 9$ for all $i$. Use generating functions!</p>

ContentLicense: CC BY-SA 3.0


问:
Finding errors in the triangle area
The lengths of sides b and c of a triangle ABC are measured accurately, while angle A is measured with an error of 1/2 degree.

If b = 12cm, c = 15cm and angle A is 30 degrees, what is the approximate value of the error in the area of this triangle?

Our teacher wanted us to think about this in the lesson. I used the $\frac12 b c \sin (A)$ formula but couldn't find it. Do you have any comments?

答:
Yes your idea is right and we can use that

$$\Delta S= \frac12 b c \sin (A+\Delta A)-\frac12 b c \sin (A)$$

with

$$\sin (A+\Delta A)=\sin (A)\cos (\Delta A)+\sin (\Delta A)\cos (A)$$

As an alternative we can use that

$$\frac{dS}{dA} =\frac12 bc \cos A \implies \Delta S \approx \frac12 bc \cos A \Delta A$$

with

$$\frac{\Delta A}{\Delta A°}= \frac{\pi}{180}$$

Title: Finding errors in the triangle area


问:
Sum of Bernoulli distributed variables
Let $N, X1, X2,...$ be independent stochastic variables where $N\sim Poisson(\lambda)$ and $X_i\sim Bernoulli(p)$ for $i = 1, 2,...$, with $\lambda>0$ & $0<p<1$.
The Compound Poisson variable $X$ is given by
\begin{equation}
  X=\sum_{j=1}^{N}X_j
 \end{equation}

Assignment: Find the distribution for $X$.

Attempted Solution: My reasoning is as follows

Each of the variables $X_j$ may assume values $x=1$ or $x=0$ with respective probabilities $p$ and $1-p$. This way the variable $X$ counts the number of "succesful" attempts, up to $N$ trials.

I think the chance to get $P(X=k)=P\left(\sum_{j=1}^{N}X_j=k\right)$ should be the chance for $P\left(\sum_{j=1}^{n}X_j=k\right)$ multiplied by $P(N=n)$. That is; it's the chance to get $k$ successes in $n$ attempts, multiplied by the chance to have those $n$ tries.

So this leads me to
\begin{align}
P(X=x) &= P\left(\{N=n\}\cap \left\{\sum_{j=1}^{n}X_j=k\right\}\right)\\
       &= P(N=n)\cdot P\left(\sum_{j=1}^{n}X_j = k\right) \text{Because they're independent}\\
\end{align}

Then I use the fact that a sum of (indepedent, parameter $p$) Bernoulli trials will follow a Binomial distribution. Thus
\begin{align}
P(X=x) &= \frac{e^{-\lambda}\lambda^n}{n!} \cdot (_{k}^{n})p^k(1-p)^{n-k}\\
       &= \frac{e^{-\lambda}\lambda^n}{n!} \cdot \frac{n!}{k!(n-k)!} p^k(1-p)^{n-k}\\
       &= \frac{e^{-\lambda}p^k\lambda^n}{k!} \cdot \frac{(1-p)^{n-k}}{(n-k)!}
\end{align}
Where I used the fact that $N\sim Poisson(\lambda)$ to find $P(N=n)$.

Thus concluding
$$P_X(x) =
\begin{cases}
 \frac{e^{-\lambda}p^k\lambda^n}{k!}\cdot\frac{(1-p)^{n-k}}{(n-k)!} & \text{for }k=1,2,3,...\\
 0     & \text{Otherwise}
\end{cases}$$
I am, however, convinced I've gotten something wrong. Namely the fact that $n$ still shows up in the expression, though I can't quite tell what I'm missing.

答:
You went the right away! But you have to consider all cases of $n\geq k$. Let $A_n=\{N=n\}$ for all $n\geq 0$. Observe that all $A_n$'s are disjoint and their union is $\Omega$. Also, observe that $P(\{X=k\}\cap A_n)=0$ when $n<k$. Now fix $k\geq 0$ and write

\begin{align}
P(X=k)&=P\bigl(\bigcup_{n=0}^{\infty}\{X=k\}\cap A_n\bigr)=\sum_{n=0}^{\infty}P(\{X=k\}\cap A_n)\\
&=\sum_{n=k}^{\infty}P(X=k\ |\ N=n)\cdot P(N=n)
\end{align}

Now $P(X=k\ |\ N=n)={n\choose k}p^k(1-p)^{n-k}$ and $P(N=n)=e^{-\lambda}\frac{\lambda^n}{n!}$. Putting all together, for $k\geq 0$

$$P(X=k)=\sum_{n=k}^{\infty}{n\choose k}p^k(1-p)^{n-k}e^{-\lambda}\frac{\lambda^n}{n!}$$

Title: Sum of Bernoulli distributed variables


问:
Unimodal Sequences
Define a unimodal sequence of weight $n$ as a sequence of positive integers $d_1d_2 \ldots d_m$ such that:

$\sum d_i = n$

For some $j$, we have $d_1 \leq d_2 \leq \ldots \leq d_j \geq d_{j+1} \geq \ldots \geq d_m$

And let a strict unimodal sequence have the same definition, except with < instead of $\leq$, and > instead of $\geq$.

In a textbook I see the following claim: "It is easy to see that the number of unimodal sequences of weight $n$ with largest term $k$ is the coefficeint of $q^n$ in $\frac{q^k}{(1 -q)(1-q^2)\ldots(1 -q^k)(1-q^{k-1})\ldots(1-q)}$." I don't see why the claim is true.

I see that in the denominator, the coefficient of a term $q^j$ must be: (number of strict unimodal sequences of weight $j$ with an even number of terms, each no larger than $k$) - (number of strict unimodal sequences of weight $j$ with an odd number of terms, each no larger than $k$). But I don't think this interpretation helps understand why the claim is true.

答:
It is best to write this generating function as
$$
\frac1{1-q}\cdot \frac1{1-q^2}\cdots \frac1{1-q^{k-1}}\cdot \frac{q^k}{1-q^k}\cdot \frac1{1-q^{k-1}}\cdots \frac1{1-q}
$$
Expand each factor as a geometric series:
$$
(1+q+q^2+\dots)\cdots (1+q^{k-1}+\dots)(q^k+q^{2k}+\dots)(1+q^{k-1}+\dots)\cdots(1+q+\dots)
$$
On the other hand, a unimodal sequence with highest term $k$ looks like
$$
(\text{sequence of 1s})(\text{sequence of 2s})\cdots(\text{sequence of $k-1$'s})(\text{nonempty sequence of ks})(\text{sequence of k-1's})\cdots
$$
Choosing the summand in each geometric series corresponds to choosing the number of repeated entries in each of these $2k-1$ sequences.

Title: Unimodal Sequences


问:
Transformation of series
Consider:

$$\sum_{j=1}^{\infty} j \left(\frac{1}{j^t} - \frac{1}{(j+1)^t}\right)$$ for $t>0$.

Can I rewrite that as:
$$\sum_{j=1}^{\infty} \frac{1}{j^t} $$

Title: Transformation of series

Body:
Noting
$$\sum_{j=1}^{N} j \left(\frac{1}{j^t} - \frac{1}{(j+1)^t}\right)=\sum_{j=1}^{N} \left(\frac{1}{j^{t-1}} - \frac{(j+1)-1}{(j+1)^t}\right)=\sum_{j=1}^{N} \left(\frac{1}{j^{t-1}} - \frac{1}{(j+1)^{t-1}}+\frac{1}{(j+1)^t}\right)=1-\frac{1}{(N+1)^{t-1}}+\sum_{j=1}^N\frac{1}{(j+1)^t}$$
and letting $N\to\infty$,
$$\sum_{j=1}^{\infty} j \left(\frac{1}{j^t} - \frac{1}{(j+1)^t}\right)=1+\sum_{j=1}^\infty\frac{1}{(j+1)^t}.$$


问:
Origins of two creative steps used in discussion of the relevance of complex numbers. From Spivak's Calculus 2nd edition.
The following is a passage from Spivak's Calculus - Ch.25 - pg 519 - 2nd ed. It revolves around the importance of complex numbers and solving for solutions:

My question revolves around where did the idea come from and what did the author ask themselves to use the substitutions:

$$x = y - \frac{b}{3} \\ x = w - \frac{p}{3w}$$

?

I see how they work, but as used plenty when teaching math, the substitutions seem to have been "pulled out of thin air". I'm trying to rectify that. So where did the notion come from to these things?

答: If, in $x^3+bx^2+cx+d$, you replace $x$ with $x+k$, then you get$$x^3+(b+3k)x^2+Mx+N\tag1$$for some numbers $M$ and $N$. So, in order that $(1)$ is of the form $x^3+\alpha x+\beta$, $k$ shall have to be such that $b+3k=0$. In other words, $k=-\frac b3$.


问:
Does a solution in $\mathbb{Q}(\sqrt{2})$ imply solution in $\mathbb{Q}$ for every system of linear equations?
Let us assume that the system of linear U equations with integers has a solution in the field $\mathbb{Q}(\sqrt{2})$. Is that true that U also has a solution in $\mathbb{Q}$?

I think that it is true because $\mathbb{Q}(\sqrt{2})$ is an subfield of $\mathbb{Q}$. Can somebody make it clear for me why is that exacty?

Thank you in advance.

答:
The opposite of what you wrote is true.

$\mathbb Q$ is a subfield of $\mathbb Q(\sqrt2)$.

$\sqrt2\in\mathbb Q(\sqrt2)$ but $\sqrt2\not\in\mathbb Q$, i.e., $\sqrt2$ is irrational.


答: $e^{n^{2}} \geq n^n$ $\Leftrightarrow $$e^{n^{2}} \geq e^{n\ln(n)} $ $\Leftrightarrow $ $ n^2 \geq n\ln(n) $ $\Leftrightarrow $ $n\geq \ln(n) $ that is correct for all $n>1$


问:
Is there a metric on $\Bbb{N}$ which makes it connected?
Not too sure where to start for this question, any help would be appreciated!

The definition of connected that I am using is:

A connected space cannot be written as the disjoint union of two nonempty open sets.

答:
Let $d$ be the supposed metric such that $\mathbb{N}$ is connnected. Then $d:\mathbb{N}^2\to\mathbb{R}^+$ is a continuous function. As such, it sends connected sets to connected sets, and so $d(\mathbb{N}^2)$ is connected. However, given that it is at most numerable, and that connected sets in $\mathbb{R}^+$ are intervals, we must have $\#d(\mathbb{N}^2)=1$. Since $d(x,x)=0$, $d(\mathbb{N}^2)=\{0\}$. This is a clear contradiction, and it generalizes to non trivial metric spaces with cardinality less than $\mathfrak{c}$

Note that there's a topology such that $\mathbb{N}$ is connected: the trivial topology, i.e. $\tau_\mathbb{N}=\{\emptyset, \mathbb{N}\}$


答:
There are countably infinite connected topological spaces, one of which I described in this answer, but there is no countably infinite connected metric space. To see this, suppose that $d$ is a metric on $\Bbb N$. Let $D=\{d(0,n):n\in\Bbb Z^+\}$; $D$ is a countable set, so there is a positive $r\in\Bbb R\setminus D$. Let $U=B(0,r)$, the open ball of radius $r$ centred at $0$; I claim that $\Bbb N\setminus U$ is also open and hence that $\langle\Bbb N,\rangle$ is not connected.

Let $n\in\Bbb N\setminus U$; then $d(0,n)>r$. Let $s=d(0,n)-r>0$; it’s easy to verify that $B(n,s)\cap U=\varnothing$, so $B(n,s)$ is an open nbhd of $n$ contained in $\Bbb N\setminus U$. And $n$ was an arbitrary element of $\Bbb N\setminus U$, so $\Bbb N\setminus U$ is open.

Title: Is there a metric on $\Bbb{N}$ which makes it connected?

Body:
Not too sure where to start for this question, any help would be appreciated!

The definition of connected that I am using is:

A connected space cannot be written as the disjoint union of two nonempty open sets.


答:
For the second part, the crucial observation (made in the 15 or 16th century - there was some priority dispute between Cardano and someone else) was that if $x=u+v$ then $x^3=u^3+v^3+3uv(u+v)$ which immediately suggested to look for $u,v$ st $u^3+v^3+q=0, 3uv=-p$ so $x^3+px+q=(u^3+v^3+q)+(3uv+p)(u+v)=0$ and then $u^3+v^3+q=0, 3uv+p=0$ lead to a  quadratic in $u^3$.

Notice that then $x=u+v=u-p/(3u)$ exactly as shown in Spivak!

Title: Origins of two creative steps used in discussion of the relevance of complex numbers. From Spivak's Calculus 2nd edition.

Body:
The following is a passage from Spivak's Calculus - Ch.25 - pg 519 - 2nd ed. It revolves around the importance of complex numbers and solving for solutions:

My question revolves around where did the idea come from and what did the author ask themselves to use the substitutions:

$$x = y - \frac{b}{3} \\ x = w - \frac{p}{3w}$$

?

I see how they work, but as used plenty when teaching math, the substitutions seem to have been "pulled out of thin air". I'm trying to rectify that. So where did the notion come from to these things?


答:
If you have a system of linear equations with integer (equiv. rational) coefficients,
$$\begin{align*}
a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n &= b_1\\
&\vdots\\
a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n &= b_m
\end{align*}$$
with each $a_{ij},b_k\in\mathbb{Z}$ (or in $\mathbb{Q}$), and this system has a solution $\mathbb{Q}(\sqrt{2})$, then it also has a solution in $\mathbb{Q}$, but not for the (incorrect, as noted by J.W. Tanner) reason you state. Every element of $\mathbb{Q}(\sqrt{2})$ can be written uniquely as $r+s\sqrt{2}$ with $r,s\in\mathbb{Q}$. So if $x_i=r_i+s_i\sqrt{2}$ is a solution, then the $j$ equation says
$$\begin{align*}
b_j &= a_{j1}(r_1+s_1\sqrt{2}) + a_{j2}(r_2+s_2\sqrt{2}) + \cdots + a_{jn}(r_n+s_n\sqrt{2})\\
&= (a_{j1}r_1+\cdots+a_{jn}r_n) + (a_{j_1}s_1+\cdots+a_{jn}s_n)\sqrt{2},
\end{align*}$$
hence
$$a_{j1}r_1+\cdots+a_{jn}r_n = b_j \text{ and }a_{j1}s_1+\cdots+a_{jn}s_n=0.$$
In particular, $x_j=r_j$ is a rational solution.

Title: Does a solution in $\mathbb{Q}(\sqrt{2})$ imply solution in $\mathbb{Q}$ for every system of linear equations?

Body:
Let us assume that the system of linear U equations with integers has a solution in the field $\mathbb{Q}(\sqrt{2})$. Is that true that U also has a solution in $\mathbb{Q}$?

I think that it is true because $\mathbb{Q}(\sqrt{2})$ is an subfield of $\mathbb{Q}$. Can somebody make it clear for me why is that exacty?

Thank you in advance.


问:
Is $\operatorname{SL}_2(\mathcal O_K)$ dense in $\operatorname{SL}_2(\mathbb R)$?
Let $K$ be a real quadratic number field of discriminant $D>0$ with $\mathcal O_K$ being its ring of integers.

There are two embeddings $K \hookrightarrow \mathbb R$ and using them $\mathcal O_K \hookrightarrow \mathbb R^2$ can be reagarded as discrete subgroup of $\mathbb R^2$. But when you regard only one embedding $\mathcal O_K \hookrightarrow \mathbb R$ is a dense subgroup of $\mathbb R$.

Now let us consider $\operatorname{SL}_2(\mathcal O_K)$. Embedded into $\operatorname{SL}_2(\mathbb R)^2$ this is still discrete. But if you regard only one embedding $\operatorname{SL}_2(\mathcal O_K) \hookrightarrow \operatorname{SL}_2(\mathbb R)$ this is not discrete anymore. For example you have

$$\left\{\left(\begin{matrix}
1 & \lambda\\
0 & 1\\
\end{matrix}\right) \in \operatorname{SL}_2(\mathcal O_K) : \lambda \in \mathcal O_K\right\}
$$
whose closure is
$$\left\{\left(\begin{matrix}
1 & x\\
0 & 1\\
\end{matrix}\right) \in \operatorname{SL}_2(\mathbb R) : x \in \mathbb R\right\}.
$$
On the other hand I'm not sure if for all $x \in \mathbb R$ the matrix $\operatorname{diag}(x,x^{-1})$ is part of the closure of $\operatorname{SL}_2(\mathcal O_K)$.

So my question is: What is the closure of $\operatorname{SL}_2(\mathcal O_K)$ in $\operatorname{SL}_2(\mathbb R)$? Is $\operatorname{SL}_2(\mathcal O_K)$ maybe dense in $\operatorname{SL}_2(\mathbb R)$?

答:
A Zariski-dense subgroup in $\mathrm{SL}_n(\mathbf{R})$ is either discrete or dense (indeed the Lie algebra of its closure is an ideal, hence 0 or everything)

Since your group contains $\mathrm{SL}_2(\mathbf{Z})$ it is Zariski-dense. Since it contains unipotent matrices with coefficients in $O_K$, it is not discrete. Hence it's dense.


问:
a≤b, b-a<ε => unique C which is A's upper bound, and B's lower bound
$$A,B\subseteq \mathbb R \quad a\in A\quad b\in B\quad \forall a,b \quad a\leq b
\\
\forall \varepsilon >0 \quad b-a<\varepsilon
$$
Prove there's a unqiue $c$, which is the upper bound of $A$, and the lower bound of $B$.

I've found a way to prove that $\inf(B) = \sup(A)$. But that's it, I have no idea how to prove that there's a unique $c$ which is both the upper bound of A, and that lower bound of B.

答:
It seems like your job is to prove that there exists a unique real number $C$ such that $C$ is an upper bound for $A$ and $C$ is a lower bound for $B$.

This breaks into two steps: proof of existence; and proof of uniqueness.

To prove existence, you write down a formula $C =$ SOMETHING, and you verify that this $C$ that you wrote down is an upper bound for $A$ and is also an upper bound for $B$. Your question contains the required formula: $C = \sup(A)=\inf(B)$; it is an upper bound for $A$ becaue $\sup(A)$ is an upper bound for $A$; and it is a lower bound for $B$ because $\inf(B)$ is a lower bound for $B$.

To prove uniqueness, you assume that you have another number, say $C'$, and you also assume that $C'$ is an upper bound for $A$ and is an upper bound for $B$; then, using these assumptions, you prove that $C'=C$. This is a proof by contradiction: assuming that $C' \ne C$, it follows that either $C' < C$ or $C' > C$, and so you break into a proof by cases. If $C' < C$ then, using $C = \sup(A)$, it follows that $C'$ is an upper bound for $A$ which is less than the least upper bound, contradiction. If $C' > C$ then, similarly using $C = \inf(B)$, it follows that $C'$ is a lower bound for $B$ which is greater than the greatest lower bound, contradiction.


问:
At a round table there are 5 gentlemen and 5 ladies. If ladies and gentlemen are to sit in alternate seat.
At a round table there are 5 gentlemen and 5 ladies. If ladies and gentlemen are to sit in alternate seats, in how many ways can they sit (in a circular arrangement)?. Im having trouble figuring out this problem, but I believe I'm on the right track. Their are 10 people and because its a circle you have to minus out one, now split into men and women so it !4/0! * !4/0 * 2.</p>

答:
First guy has $10$ seats to choose from.

Remaining guys have $4!$ ways to sit in their $4$ chairs.

There are $5!$ ways of seating the $5$ women in the remaining $5$ chairs

$10\cdot 4! \cdot 5! = 28800$ ways


问:
How to find the correct formula to calculate the sum of a geometric series.
I have a formula for a series which looks like this:

$\sum_{i=2}^{8}(-2)^i$

And I see that this series gives me the following output:

4 - 8 + 16 - 32 + 64 - 128 + 256

Which gives a sum of 172 - assuming I have done the calculations correctly.

However, I also need to find a formula to determine the sum, and I'm wondering if I'm on the right path here:

$\sum_{i=0}^{7}2^i = \frac{2^{7^+1}-1}{2-1} $

This is a formula I found to determine the sum of a geometric series. But I'm a bit thrown off by the task I'm trying to solve above.

I tried approaching the formula as shown below:

$ \frac{(-2)^{6}-1}{-2-1} $

But seing as the formula I have been working on above is a negative integer I'm having some difficulties finding the right approach to calculate the sum with the correct formula.

Am I using the wrong formula or am I simply just using it incorrectly?

Body:
We have that for any $r\neq 1$

$$\sum_{i=0}^{n}r^i = \frac{r^{n+1}-1}{r-1}$$

then

$$\sum_{i=0}^{8}(-2)^i = \frac{(-2)^{9}-1}{-2-1}=171$$

and

$$\sum_{i=2}^{8}(-2)^i =\sum_{i=0}^{8}(-2)^i-\sum_{i=0}^{1}(-2)^i=171-(1-2)=172$$


答:
The problem isn’t overlaps: it’s restricting the values to the range from $0$ through $9$. You’re looking for the number of solutions in non-negative integers to the equation

$$x_1+x_2+x_3+x_4+x_5+x_6=30\tag{1}$$

with the added requirement that $x_k\le 9$ for $k=1,\dots,6$: each of those solutions defines one of the numbers that you’re trying to count, and vice versa. The number of solutions without the upper bound restriction is, as you say,

$$\binom{30+6-1}{6-1}=\binom{35}5\;.$$

However, some of those solutions require ‘digits’ greater than $9$. Start by counting the solutions in non-negative integers to $(1)$ that have $x_1\ge 10$. Those are clearly in one-to-one correspondence with solutions in non-negative integers to

$$y_1+x_2+x_3+x_4+x_5+x_6=20\;,$$

where $y_1=x_1-10$, and you know how to compute their number. Call that number $n_1$. There are just as many solutions to $(1)$ that violate the upper bound on $x_2$, just as many again that violate the upper bound on $x_3$, and so on, so a better approximation to the solution to the original problem is

$$\binom{35}5-6n_1\;.$$

Of course this overcorrects, since it’s possible for a solution to $(1)$ to violate two of the upper bound constraints at once. You’ll have to calculate the number $n_2$ of solutions that have $x_1\ge 10$ and $x_2\ge 10$ and then add back the appropriate multiple of $n_2$. And since it’s actually possible to violate as many as three of the constraints at once, you’ll have to make one further inclusion-exclusion correction.

Title: Counting the numbers between $1$ and $1,000,000$ whose digits sum to $30$

Body:
What's the number of numbers between $1$ and $1,000,000$ whose digits sum is $30$?

So I thought of this as a stars and sticks problem, so in the case you have $35\choose 5$ numbers whose sum is $30$. But obviously this number of numbers includes many overlaps (if for instance the requested sum was $8$, then $80=800=8000=134=143=431$ etc.). How do I get rid of the overlaps (inclusion-exclusion)?

Thanks in advance for any assistance!


问:
An interesting problem with "decomposing" natural numbers.
Consider the following one-person game:

A player starts with score $0$ and writes the
number $20$ on an empty whiteboard. At each step, she may erase any one integer (call it $a$)
and writes two positive integers (call them $b$ and $c$) such that $b + c = a$. The player then
adds $b × c$ to her score. She repeats the step several times until she ends up with all $1$s on
the whiteboard. Then the game is over, and the final score is calculated.

Example: At the first step, a player erases $20$ and writes $14$ and $6$, and gets a score of
$14 × 6 = 84$. In the next step, she erases $14$, writes $9$ and $5$, and adds $9 × 5 = 45$ to her
score. Her score is now $84 + 45 = 129$. In the next step, she may erase any of the remaining
numbers on the whiteboard: $5$, $6$ or $9$. She continues until the game is over.

Alya and Bob play the game separately. Alya manages to get the highest possible final score.
Bob, however, manages to get the lowest possible final score. What is the difference between
Alya’s and Bob’s final scores?

I tried to "decompose" into a few numbers and I get the same scores. I am not sure how to prove the conjecture that any numbers will yield the same score no matter which path is taken.

答:
Suppose that we represent a number $n$ on the whiteboard by $n$ distinct objects. When we split $a$ into $b+c$, we put $b$ of the objects in one group, and $c$ of the objects in the other group.

Then we can represent the $b\cdot c$ points we get for the split as follows: for every pair of objects that used to be in the same group, but are now in different groups, we get a point.

At the beginning, all $20$ objects are in the same group. At the end, all $20$ objects are in different groups, so we must have gotten $\binom{20}{2}$ points for separating them.


问:
Intuition of Artin's Linear Independence Theorem
Let $G$ be a group and $k$ be a field. A character of $G$ is a group homomorphism $G \to k^{\times}$.

Theorem (Artin). Distinct characters $\chi_1, \dots, \chi_n : G \to k^\times$ are linearly independent in $\operatorname{Map}(G,k)$.

(Special case in a different setting: Let $L/K$ be a finite separable field extension, $\tau : K \to \overline{L}$ an embedding, then there are exactly $n = [L:K]$ embeddings $\sigma_1, \dots, \sigma_n : L \to \overline{L}$ preserving $\tau$. These are linearly independent over $\Omega$.)

But why? I know the standard proof but I fail to really grasp why this statement should be true. The best I can come up with is the following: Take a linear combination $$ a_1 \chi_1 + \dots + a_n \chi_n = 0, $$ then by plugging in elements from $G$, we get a bunch of linear relations, e.g. by plugging in the identity element $e \in G$, we get $a_1 + \dots + a_n = 0$. Since those are a lot of relations, they should eventually give us $a_1 = \dots = a_n = 0$.

However, this is extremely vague. Does anyone have a better intuitive explanation of this result?

答:
You meant $G$ is an arbitrary infinite group. Viewing the $\chi_j$ as characters on the abelian group $G/\cap_j \ker(\chi_j)$, they are assumed distinct thus they must disagree on some finitely generated subgroup $\langle s_1,\ldots,s_n\rangle$.

Assuming $a_1\ne 0$, take a polynomial $f(x)=\sum_{k=0}^K c_k x^k\in k[x]$ such that $f(\chi_1(s_1))=1$ and $f(\chi_j(s_1))=0$ for $\chi_j(s_1)\ne \chi_1(s_1)$. Then for all $g$, $$\sum_{l,\chi_l(s_1)=\chi_1(s_1)}a_l \chi_l(g)=\sum_{j=1}^n a_j f(\chi_j(s_1)) \chi_j(g)=\sum_{k=0}^K c_k \sum_{j=1}^n a_j \chi_j(s_1^k g)=0$$
Thus we get a linear dependence between the characters agreeing with $\chi_1$ at $s_1$, repeating with $s_2,s_3,\ldots$ we'll reach a contradiction, ie. that two characters are the same on $\langle s_1,\ldots,s_n\rangle$.


答:
Suppose you perform Gaussian elimination over $\mathbb{Q}$ on the augmented matrix corresponding to the original system.  Then each step is also valid over $\mathbb{Q}(\sqrt{2})$ and thus results in an equivalent system whether the field you are working over is $\mathbb{Q}$ or $\mathbb{Q}(\sqrt{2})$.

At the end, once you have reached a matrix in row echelon form, or in reduced row echelon form (and either condition is independent of the exact scalar field), then over either field, a solution exists if and only if no row in the echelon form matrix corresponds to an equation $0 x_1 + \cdots + 0 x_n = b$ with $b \ne 0$.  This condition, too, is independent of the exact scalar field.


答:
Sometimes you can find close formed solutions for values of sums by noticing patterns. For example, we have $S = \sum_{i=0}^n(-2)^i = \sum_{i=0}^n(-1)^i(2)^i$, but what is $2S$? We can see that $2S = \sum_{i=0}^n(-1)^i(2)^{i+1} = \sum_{i=1}^{n + 1}(-1)^{i-1}(2)^i = \sum_{i=1}^{n + 1}-(-1)^{i}(2)^i = 1 - S + (-1)^n2^{n + 1}$.

So $3S = 1 + (-1)^n2^{n+1} \implies S = \frac{1 + (-1)^n2^{n+1}}{3}$.

You can use this to get the sum in any interval by simply subtracting.

Title: How to find the correct formula to calculate the sum of a geometric series.

Body:
I have a formula for a series which looks like this:

$\sum_{i=2}^{8}(-2)^i$

And I see that this series gives me the following output:

4 - 8 + 16 - 32 + 64 - 128 + 256

Which gives a sum of 172 - assuming I have done the calculations correctly.

However, I also need to find a formula to determine the sum, and I'm wondering if I'm on the right path here:

$\sum_{i=0}^{7}2^i = \frac{2^{7^+1}-1}{2-1} $

This is a formula I found to determine the sum of a geometric series. But I'm a bit thrown off by the task I'm trying to solve above.

I tried approaching the formula as shown below:

$ \frac{(-2)^{6}-1}{-2-1} $

But seing as the formula I have been working on above is a negative integer I'm having some difficulties finding the right approach to calculate the sum with the correct formula.

Am I using the wrong formula or am I simply just using it incorrectly?


问:
How do you find a square on a grid from a position?
The title might be a bit confusing, since I didn't know how to put this into one sentence.

I have a 10x10 grid and every square on the grid is 100 pixels (this is a programming problem) from edge to edge. If I have a position where the x and y-value represent pixels away from the top or left side of the grid, how can I determine which square on the grid contains the position?

答: The simplest method would be to use the ceiling function: that is, $\lceil x \rceil$ is the smallest integer which is not smaller than $x$. So, supposing the squares are numbered $1$ to $10$, a pair of coordinates $(x,y)$ becomes $(\lceil \frac{x}{100} \rceil , \lceil  \frac{y}{100}\rceil )$ - telling us the "square" coordinates. Take, for example, $(153, 814)$. Then the corresponding square is $(\lceil 1.53\rceil,\lceil 8.14 \rceil ) = (2, 9)$, i.e. the square that is second from the left and 9th from the bottom (alternatively, second from the top).


问:
Are there any non-discrete definitions for the size of a matrix?
Throughout my math education I have noticed that in order to solve a difficult problem with one set of numbers it helps to move to a larger encompassing set. For example, subtracting some natural numbers, $\mathbb{N}$ , requires the integers,  $\mathbb{Z}$ (e.g. $3-4$ would be meaningless in a world with only the natural numbers). This pattern seems to continue, from the integers to the real numbers to the complex numbers. There also seems to be another pattern that holds with the idea of scalars to matrices to tensors, etc. Each next set holding (or generalizing) the previous.

What I have noticed--in my limited math education--is that matrices stick to natural numbers in their dimensionality. That is: $$i,j \in \mathbb{N},\mathbb{R}^{i\times j}$$

My question boils down to this:

Can matrix $A \in \mathbb{R}^{i\times j} : i,j \in \mathbb{C}$?

If not why not?

If so, then what does it mean for one of these objects to have a non-natural dimension? For example, a vector, $v \in \mathbb{R}^{- \pi/2 \times 1} $ or a matrix $A \in \mathbb{R}^{0.5 \times -1} $? Is such an object even able to be represented?

答: If $A$'s indices can be any complex numbers, $A$ becomes a linear operator that maps a function $f$ of domain $\Bbb C$ to $\int_{\Bbb C^2}A(x, \, y)f(y) dy$. This involves regarding each such function $f$ as a vector in a space of dimension $|\Bbb C|$.


问:
X-sided dice probability
I have an $x$-sided dice and I roll it $y$ times.

What is the probability that I will see at least $z$ of the $x$ sides?

e.g. If I rolled a $6$-sided dice $8$ times, what is the probability I see at least $4$ of the sides?

But I want to do with much bigger numbers

Specifically, I want to know  what is probability I see at least $z$ of the $160,000$ sides if I rolled a $160,000$-sided dice $25,000$ times.

Thanks in advance!

答:
There is an exact solution involving Stirling numbers of the second kind and if you wanted to do the calculations for throwing eight $6$-sided dice then the probabilities would be:

$1$ face: $\left\{{8\atop 1}\right\}\frac{6!}{6^8 (6-1)!} = \frac{6}{1679616}$

$2$ faces: $\left\{{8\atop 2}\right\}\frac{6!}{6^8 (6-2)!} = \frac{3810}{1679616}$

$3$ faces: $\left\{{8\atop 3}\right\}\frac{6!}{6^8 (6-3)!} = \frac{115920}{1679616}$

$4$ faces: $\left\{{8\atop 4}\right\}\frac{6!}{6^8 (6-4)!} = \frac{612360}{1679616}$

$5$ faces: $\left\{{8\atop 5}\right\}\frac{6!}{6^8 (6-5)!} = \frac{756000}{1679616}$

$6$ faces: $\left\{{8\atop 6}\right\}\frac{6!}{6^8 (6-6)!} = \frac{191520}{1679616}$

making the probability of $4$ or more faces $\frac{1559880}{1679616} \approx 0.9287$

This can become intractable for large $x$ and $y$.  An alternative approach is a recurrence with $$p(x,y,z) = \frac{z}{x}p(x,y-1,z) + \frac{x-z+1}{x}p(x,y-1,z-1)$$ starting with $p(x,1,1)=1$ and $p(x,1,z)=0$ for $z \not=1$.

Suppose we start with your $x=160000$ and $y=25000$ and suppose we want to find for example $\mathbb P(Z \ge 23100)=\sum\limits_{z=23100}^{160000} p(x,y,z)$.  Then we could use the following R code:

```<code>x <- 160000
maxy <- 25000
atleastz <- 23100
p <- c(1, rep(0, x-1))
for (y in 2:maxy){ p <- (1:x)/x * p + (x-(1:x)+1)/x * c(0,p[-x]) }
sum(p[atleastz:x])
# 0.8783097
</code>```

Even that takes a little time with large $x$ and $y$. We could instead use a normal approximation (and a continuity correction) starting from the exact results $$\mu=E[Z] = x \left(1- \left(1-\frac1x\right)^y\right)$$ $$\sigma^2=\mathrm{Var}(Z)=x\left(1-\frac1x\right)^y + \left(x^2-x\right)\left(1-\frac2x\right)^y - x^2\left(1-\frac1x\right)^{2y}$$  which with your $x=160000$ and $y=25000$ are a mean of $23144.81$ and variance of $1506.32$ (i.e. a standard deviation of $38.81$).

We then want $\mathbb P(Z \ge z)\approx 1-\Phi\left(\frac{z-\frac12 - \mu}{\sigma}\right)$.  With R this might suggest

```<code>x <- 160000
y <- 25000
atleastz <- 23100
m <- x*(1-(1-1/x)^y)
v <- x*(1-1/x)^y + (x^2-x)*(1-2/x)^y - x^2*(1-1/x)^(2*y)
1 - pnorm((atleastz - 1/2 - m)/sqrt(v))
# 0.8785072
</code>```

which in this example is very close to the exact result.

Title: X-sided dice probability

Body:
There is an exact solution involving Stirling numbers of the second kind and if you wanted to do the calculations for throwing eight $6$-sided dice then the probabilities would be:

$1$ face: $\left\{{8\atop 1}\right\}\frac{6!}{6^8 (6-1)!} = \frac{6}{1679616}$

$2$ faces: $\left\{{8\atop 2}\right\}\frac{6!}{6^8 (6-2)!} = \frac{3810}{1679616}$

$3$ faces: $\left\{{8\atop 3}\right\}\frac{6!}{6^8 (6-3)!} = \frac{115920}{1679616}$

$4$ faces: $\left\{{8\atop 4}\right\}\frac{6!}{6^8 (6-4)!} = \frac{612360}{1679616}$

$5$ faces: $\left\{{8\atop 5}\right\}\frac{6!}{6^8 (6-5)!} = \frac{756000}{1679616}$

$6$ faces: $\left\{{8\atop 6}\right\}\frac{6!}{6^8 (6-6)!} = \frac{191520}{1679616}$

making the probability of $4$ or more faces $\frac{1559880}{1679616} \approx 0.9287$

This can become intractable for large $x$ and $y$.  An alternative approach is a recurrence with $$p(x,y,z) = \frac{z}{x}p(x,y-1,z) + \frac{x-z+1}{x}p(x,y-1,z-1)$$ starting with $p(x,1,1)=1$ and $p(x,1,z)=0$ for $z \not=1$.

Suppose we start with your $x=160000$ and $y=25000$ and suppose we want to find for example $\mathbb P(Z \ge 23100)=\sum\limits_{z=23100}^{160000} p(x,y,z)$.  Then we could use the following R code:

x <- 160000
maxy <- 25000
atleastz <- 23100
p <- c(1, rep(0, x-1))
for (y in 2:maxy){ p <- (1:x)/x * p + (x-(1:x)+1)/x * c(0,p[-x]) }
sum(p[atleastz:x])
# 0.8783097

Even that takes a little time with large $x$ and $y$. We could instead use a normal approximation (and a continuity correction) starting from the exact results $$\mu=E[Z] = x \left(1- \left(1-\frac1x\right)^y\right)$$ $$\sigma^2=\mathrm{Var}(Z)=x\left(1-\frac1x\right)^y + \left(x^2-x\right)\left(1-\frac2x\right)^y - x^2\left(1-\frac1x\right)^{2y}$$  which with your $x=160000$ and $y=25000$ are a mean of $23144.81$ and variance of $1506.32$ (i.e. a standard deviation of $38.81$).

We then want $\mathbb P(Z \ge z)\approx 1-\Phi\left(\frac{z-\frac12 - \mu}{\sigma}\right)$.  With R this might suggest

x <- 160000
y <- 25000
atleastz <- 23100
m <- x*(1-(1-1/x)^y)
v <- x*(1-1/x)^y + (x^2-x)*(1-2/x)^y - x^2*(1-1/x)^(2*y)
1 - pnorm((atleastz - 1/2 - m)/sqrt(v))
# 0.8785072

which in this example is very close to the exact result.


答:
A perhaps related result to what you're after, if not a direct answer:

Given any two sets $P$ and $Q$, you can from the vector spaces $\mathbb{R}^P$ and $\mathbb{R}^Q$ consisting of all functions from $P$ (resp. $Q$) to $\mathbb{R}$. Then the matrices representing linear maps from $\mathbb{R^P} \to \mathbb{R}^Q$ are given by elements of $\mathbb{R}^{P \times Q}$: functions from $P \times Q \to \mathbb{R}$.

These vector spaces have dimension other than natural numbers (say, if $P$ and $Q$ are infinite) but they do not have dimensions like what you might be looking for: i.e. they are not "complex dimensional", etc.
Instead, these vector spaces can take cardinal numbers as their dimension.

As far as a "continuous" analogue of dimension goes, I don't know of any reasonable way to make sense of a "vector space of dimension $\frac{1}{2}$", let alone one of dimension $2+i$. It also strikes me as unlikely that such a concept exists. That said, I haven't ever thought to look into such things, and I've been surprised before. Who knows, maybe you'll be the person to develop such a notion!

Edit:

After a short google, it looks like this is something that people have thought of before (at least for rational dimension), but the machinery is rather complex. See here for instance.

I hope this helps ^_^

Title: Are there any non-discrete definitions for the size of a matrix?

Body:
Throughout my math education I have noticed that in order to solve a difficult problem with one set of numbers it helps to move to a larger encompassing set. For example, subtracting some natural numbers, $\mathbb{N}$ , requires the integers,  $\mathbb{Z}$ (e.g. $3-4$ would be meaningless in a world with only the natural numbers). This pattern seems to continue, from the integers to the real numbers to the complex numbers. There also seems to be another pattern that holds with the idea of scalars to matrices to tensors, etc. Each next set holding (or generalizing) the previous.

What I have noticed--in my limited math education--is that matrices stick to natural numbers in their dimensionality. That is: $$i,j \in \mathbb{N},\mathbb{R}^{i\times j}$$

My question boils down to this:

Can matrix $A \in \mathbb{R}^{i\times j} : i,j \in \mathbb{C}$?

If not why not?

If so, then what does it mean for one of these objects to have a non-natural dimension? For example, a vector, $v \in \mathbb{R}^{- \pi/2 \times 1} $ or a matrix $A \in \mathbb{R}^{0.5 \times -1} $? Is such an object even able to be represented?


问:
Simplification of Complex number summation
How does the author of this book make these simplifications from left to right? It doesn’t seem obvious. Here $h,\alpha$ are real numbers and $N$ is a natural number

$$
\left|\sum_{n=1}^{N}e^{2\pi i h n \alpha}\right|\le \frac{2}{|e^{2\pi i h \alpha}-1|}= \frac{1}{|\sin(\pi h \alpha)|}
$$

答:
Set
$$
q=e^{2\pi ih\alpha}
$$
then your sum is
$$
\sum_{n=1}^Nq^n=\sum_{n=0}^Nq^n-1=\frac{1-q^{N+1}}{1-q}-1=q\frac{1-q^{N}}{1-q}
$$
Can you conclude?


答:
$\sum_{n=1}^Ne^{2\pi ih n \alpha}=\frac{e^{2\pi ih (N+1) \alpha}-e^{2\pi i h \alpha}}{e^{2\pi h i \alpha}-1}$ since we have a geometric series.

Now notice that the numerator is at most $2$ in absolute value which gets you the first inequality, while the denominator absolute value is $|2\sin \pi h \alpha|$ by the double angle formula ($\cos 2y -1=-2\sin^2 y, i\sin 2y=2i\sin y \cos y, y=\pi i h \alpha$, etc), so one gets the second equality

Title: Simplification of Complex number summation

Body:
How does the author of this book make these simplifications from left to right? It doesn’t seem obvious. Here $h,\alpha$ are real numbers and $N$ is a natural number

$$
\left|\sum_{n=1}^{N}e^{2\pi i h n \alpha}\right|\le \frac{2}{|e^{2\pi i h \alpha}-1|}= \frac{1}{|\sin(\pi h \alpha)|}
$$


问:
Homology of Möbius Strip
How does one calculate the homology groups of the Möbius strip?

I'm thinking of two methods.

Use cellular homology. I tried to draw a delta-complex structure of the Möbius strip but I'm not sure if I'm right? I basically have a rectangle with opposite ends identified, so vertices (top-down) on the left are $a$ and $b$. On the right, they are $b$ and $a$. I know that there is an edge $e$ that joins from $b$ to $a$ and this is for both the left and right side of the rectangle. But this is not yet a delta complex structure, so I feel like I need to draw another edge across the rectangle from bottom left to top right, connecting $b$ to $b$. But how are these remaining 3 edges labelled? If I label the top and bottom edge, I think I'm creating another surface - the torus, RP2 or Klein bottle and so that's not the way to go. Does it mean this method is not possible?

Use $H_n(X^k,X)$ somehow, where $X^k$ is the $k$ skeleton of $X$. But I don't quite know how to proceed with this.

Any pointers in the right direction is greatly appreciated. Thanks!

答:
Take the usual paper strip that you would glue to make a Möbius strip.  If you want to get a simplicial complex, draw a line diagonally from the top corner on the left to the bottom corner on the right, so your paper strip is a union of two triangles.

Your strip now has two triangular faces, five 1-simplices (the four edges of the paper strip, together with the line you drew to divide it into two triangles), and 4 vertices.  But when you glue you identify the two edges at either end of the strip, so for the Möbius band there are two faces, four 1-simplices, and 2 vertices.

Now just write down the corresponding simplicial chain complex and compute away!

Title: Homology of Möbius Strip


答:
Here’s a visual proof, to complement the algebra of other answers:

When you start the game (from 20), draw a “staircase” shape like in the figure, but with 19 squares in the base (so also 19 squares high).  As you play, for each number on the board you’ll always have a corresponding staircase, with base and height 1 less than that number.  Each turn, when you split up a number as $n = b+c$, split up its staircase as shown in the picture; that gives you a $b \times c$ rectangle, plus two smaller staircases for the resulting numbers $b$ and $c$.  The area of the rectangles is your score so far.  When all the numbers left are 1’s, then you’ve converted the whole original staircase into rectangles — so your final score is the total area of the original staircase.

This area, the number of squares in the staircase of base $n-1$, is given by the formula $\frac{n(n-1)}{2}$, as noted in other answers. This is a famous formula, and if you haven’t seen it before, it can be explained by the fact that two such staircases fit together into an $n \times (n-1)$ rectangle.

Title: An interesting problem with "decomposing" natural numbers.

Body:
Consider the following one-person game:

A player starts with score $0$ and writes the
number $20$ on an empty whiteboard. At each step, she may erase any one integer (call it $a$)
and writes two positive integers (call them $b$ and $c$) such that $b + c = a$. The player then
adds $b × c$ to her score. She repeats the step several times until she ends up with all $1$s on
the whiteboard. Then the game is over, and the final score is calculated.

Example: At the first step, a player erases $20$ and writes $14$ and $6$, and gets a score of
$14 × 6 = 84$. In the next step, she erases $14$, writes $9$ and $5$, and adds $9 × 5 = 45$ to her
score. Her score is now $84 + 45 = 129$. In the next step, she may erase any of the remaining
numbers on the whiteboard: $5$, $6$ or $9$. She continues until the game is over.

Alya and Bob play the game separately. Alya manages to get the highest possible final score.
Bob, however, manages to get the lowest possible final score. What is the difference between
Alya’s and Bob’s final scores?

I tried to "decompose" into a few numbers and I get the same scores. I am not sure how to prove the conjecture that any numbers will yield the same score no matter which path is taken.


问:
Question about Galois Theory and Cyclic Extension.
I'm studying Galois Theory and I was thinking about something. If I have a Cyclic extension $F/E$ then $[F:E]< \infty?$

Remember that $F/E$ is a cyclic extension if $Gal(F/E)$ is cyclic and $F/E$ is galois (it doesn't implies $F/E$ finite, we just have $F/E$ normal and separable).

答:
It depends on what you mean by "cyclic" in the infinite case. As Mindlack says, a Galois group must be profinite, and infinite profinite groups are uncountable, so $\mathbb{Z}$ is never a Galois group.

However, the profinite completion $\widehat{\mathbb{Z}}$ of $\mathbb{Z}$ does occur as a Galois group (for example of any finite field), and we might say that such an extension is "topologically cyclic" in the sense that $\widehat{\mathbb{Z}}$ contains $\mathbb{Z}$ as a dense subgroup.


问:
find equation of plane.
Let

. Show that the curve with parameterization

lies in a plane, and find an equation of the plane.

答:
Hint: If you know three points in the plane, you can find the plane, right? Well, plug in $u = -1, 0, 1$ to get three points.

Now that you know what the plane HAS to be, you can show that the entire curve $r$ is contained in it without too much difficulty.

Title: find equation of plane.


问:
Equivalences of definitions of submanifolds in $\mathbb{R^n}$
A subset $M \in \mathbb{R}^n$ is called a smooth k-dimensional submanifold of $\mathbb{R}^n$, $k \leq n$, if any point $x \in M$ has a neighborhood $O_x$ in $\mathbb{R}^n$ in which $M$ is described in one of the following ways:

(1) there exists a smooth vector-function $$F:O_x \to \mathbb{R}^{n-k}, \text{  } rank \frac{dF}{dx}|_q=n-k $$
such that $O_x \cap M = F^{-1}(0)$

(2) there exists a smooth vector-function $$f:V_0 \to \mathbb{R}^{n}$$ from a neighborhood of the origin $0 \in V_0 \subset \mathbb{R}^k$  with $$f(0)= x \text{   and   } rank \frac{df}{dx}|_0=k $$
such that $f: V_0 \to O_x \cap M$ is homeomorphism.

(3) there exists a smooth vector-function $$\Phi:O_x \to O_0 \subset \mathbb{R}^{n},$$ onto a neighborhood of the origin  $0 \in O_0 \subset \mathbb{R}^n$  with $$\text{  } rank \frac{d \Phi}{dx}|_x=n $$
such that $ \Phi(O_x \cap M)= \mathbb{R}^k \cap O_0$

I am trying to show the equivalence of these definitions and my first question is why is each definition imposing itself on the rank?

答:
$(1)$ and $(2)$ are equivalent and are adequate definitions, but $(3)$ is too weak to characterize a submanifold.

Let us first introduce some notation.

For a smooth map $\psi : U \to V$ between open subsets $U \subset \mathbb R^m$ and $V \subset \mathbb R^p$ let us write $\psi'(x)$ for the Jacobian matrix of $\psi$ at $x$. This is what you denote as $\dfrac{d\psi}{dx} \mid_x$.

Let $\mathbb R^{k,n} = \{(x_1,\ldots,x_n) \in \mathbb R^n \mid x_{k+1} = \ldots = x_n =  0 \}$. Then $\mathbb R^{k,n} \subset \mathbb R^n$ whereas  $\mathbb R^k \subset \mathbb R^n$ does not make sense (or is a serious abuse of notation).

Let us call a subset $M \subset \mathbb R^n$ a $k$-dimensional smooth submanifold of $\mathbb R^n$ of type $(1) - (5)$ if each $x \in M$ satisfies

(1) There exists a smooth $F : O_x \to \mathbb{R}^{n-k}$ defined on an open neighborhood $O_x$ of $x$ in $\mathbb R^n$ such that $\operatorname{rank} F'(x) = n-k$ and $O_x \cap M = F^{-1}(0)$.

(2) There exists a smooth $f : V_0 \to \mathbb R^n$ defined on an open neighborhood of $0$ in $\mathbb{R}^k$  such that $f(0)= x$ and $\operatorname{rank} f'(0) = k$, $f(V_0)$ is an open subset of $M$ and $f : V_0 \to f(V_0)$ is a homeomorphism.

(3) There exists a smooth $\phi : O_x \to O_0$ from an open neighborhood $O_x$ of $x$ in $\mathbb{R}^{n}$ onto an open subset $O_0 \subset \mathbb{R}^n$ such $\phi(x) = 0$, $\operatorname{rank} \phi'(x) = n$ and $\phi(O_x \cap M)= \mathbb{R}^{k,n} \cap O_0$.

(4) There exists a smooth $\phi : O_x \to \mathbb R^n$ defined on an open neigborhood $O_x$ of $x$ such that $\operatorname{rank} \phi'(x) = n$ and  $\phi^{-1}(\mathbb R^{k,n}) =  O_x \cap M$.

(5) There exists a diffeomorphism $h : O_x \to V$ between an open neigborhood $U_x$ of $x$ in $\mathbb R^n$ and an open subset $V \subset \mathbb R^n$ such that $h(O_x \cap M) = \mathbb R^{k,n} \cap V$.

In my opinion the most natural definition is (5). If we want, in (5) we can moreover require that $h(x) = 0$. To see this, note that $h(x) \in \mathbb R^{k,n}$. The translation $t_{-h(x)} : \mathbb R^n \to \mathbb R^n, t_{-h(x)}(y) = y - h(x)$, is a diffeomorphism such that $t_{-h(x)}(\mathbb R^{k,n})  = \mathbb R^{k,n}$, thus $h^* = t_{-h(x)} \circ h : U_x \to V^* = t_{-h(x)}(V)$ will do what we desire.

The same is true for (4): We can require that $\phi(x) = 0$.

Now let us observe that type $(3)$ submanifolds are not what we expect. As an example take $M  = M_1 \times \{0\} \subset \mathbb R^2$ with $M_1 = (-\infty,1]  \cup (2,\infty) \subset \mathbb R$. This satisfies $(3)$: For all $x \in M' = (-\infty,1) \times \{0\} \cup (1,\infty) \times \{0\}$ we may take $O_x = (-\infty,1) \times \mathbb R \cup (1,\infty) \times \mathbb R$, $O_0 = O_x$ and $\phi = id$. For $x = (1,0)$ we take $O_x = O_0 = \mathbb R^2$ and $\phi(x_1,x_2) = (x_1^3 - 9x_1,x_2)$. Then $\phi'(x)$ is a diagonal matrix with entries $3x_1^2-9$ and $1$ which has rank $2$ execpt for $x_1 = \pm \sqrt 3$. In particular $\operatorname{rank} \phi'(1,0) = 2$. The function $\phi_1 : \mathbb R \to \mathbb R,\phi_1(x_1) = x_1^3-9x_1$, has the property $\phi_1(x_1) \to \pm \infty$ as $x_1 \to \pm \infty$. Hence by the IVT $(-\infty,-8] = (-\infty,\phi_1(1)] \subset \phi_1((-\infty,1])$ and $(-10,\infty) = (\phi_1(2),\infty) \subset \phi_1(2,\infty)$. Hence $\phi_1(M_1) = \mathbb R$, thus $\phi$ maps $\mathbb R^2$ onto $\mathbb R^2$ and $\phi(M \cap \mathbb R^2)  = \phi(M) = \phi_1(M_1) \times \mathbb \{0\} = \mathbb R \times \{0\} = \mathbb R^{1,2} = \mathbb R^{1,2} \cap \mathbb R^2$.

The problematic point is the boundary point $(1,0)$ of $M$: It prevents $M$ from being a manifold, but satisfies $(3)$.

The correct substitute for $(3)$ is $(4)$. Note, by the way, that $(5)$ trivially implies $(3)$.

Let us show the equivalence of $(1), (2), (4), (5)$.

$(4) \Rightarrow (5)$: It is well-known from multivariable calculus that $\operatorname{rank} \psi'(x) = n$ implies that that there exist open neigborhoods $U_x \subset O_x$ of $x$ and $V \subset \mathbb R^n$ of $\psi(x)$ such that $\psi(U_x) = V$ and $h = \psi \mid_{U_x}: U_x \to V$ is a diffeomorphism. Let us prove $h(U_x \cap M) = \mathbb R^k \cap V$. We have $h(U_x \cap M) =  \psi(U_x \cap M) \subset   \psi(O_x \cap M) = \psi(\psi^{-1}(\mathbb R^k)) \subset \mathbb R^k$, thus $h(U_x \cap M) \subset \mathbb R^k \cap V$ since $h(U_x \cap M) \subset h(U_x) = V$. Moreover $h^{-1}(\mathbb R^k \cap V) \subset \psi^{-1}(\mathbb R^k \cap V) \subset \psi^{-1}(\mathbb R^k) = O_x \cap M$, thus $h^{-1}(\mathbb R^k \cap V) \subset U_x \cap M = U_x \cap (O_x \cap M)$ since $h^{-1}(\mathbb R^k \cap V) \subset h^{-1}(V) = U_x$. Therefore $\mathbb R^k \cap V = h(h^{-1}(\mathbb R^k \cap V)) \subset h(U_x \cap M)$.

$(5) \Rightarrow (4)$: Take $\phi = i \circ h$ with inclusion map $i : V \to \mathbb R^n$. Clearly $\operatorname{rank} \phi'(x) = n$. Moreover $\phi^{-1}(\mathbb R^{k,n}) = h^{-1}(i^{-1}(\mathbb R^{k,n})) = h^{-1}(\mathbb R^{k,n} \cap V)$.

$(5) \Rightarrow (1)$: Let $p : \mathbb R^n \to \mathbb R^{n-k}$ denote the projection onto the first $n-k$ coordinates. We have $\operatorname{rank} p'(y) = n-k$ for all $y$. But then $F = p \mid_V \circ h$ has the property $\operatorname{rank} F'(q) = n-k$ for all $q \in U$. Clearly $p^{-1}(0) = \mathbb R^k$, hence $F^{-1}(0) = h^{-1}(p_V^{-1}(0)) = h^{-1}(\mathbb R^k \cap V)  = U \cap M$.

$(1) \Rightarrow (4)$: The $(n-k) \times n$ matrix $F'(x)$ has rank $n-k$, thus among its $n$ column vectors $a_j$ we can pick $n-k$ linearly independent vectors $a_{j_1},\ldots,a_{j_{n-k}}$ with $1 \le j_1 \le j_2 \le \ldots \le j_{n-k} \le n$. Write $C  = \{j_1,\ldots,j_{n-k}\}$ and $D = \{ 1, \ldots, n\} \setminus C = \{r_1, \ldots,r_k\}$ with $1 \le r_1 \le r_2 \le \ldots \le r_k \le n$. Define
$$\psi : O_x \to \mathbb R^n, \psi_r(x_1,\ldots,x_n) = \begin{cases}  F_i(x_1,\ldots,x_n) & r = j_i \in C \\ x_r & r\in D \end{cases}$$
For $r \in D$ the $r$-th row of $\mathcal A  = \psi'(x)$ has the form $(0 \ldots 0 \phantom{.} 1 \phantom{.} 0 \ldots 0)$ where the entry $1$ is at position $r$. We can compute $\det \mathcal A$ by Laplace expansion along rows. Starting with  $r = r_k$ we get $\det \mathcal A  = (-1)^{r_k + r_k} \det \mathcal A_{r_k  r_k} = \det \mathcal A_{r_k  r_k}$, where $\mathcal A_{r_k  r_k}$ is obtained from $\mathcal A$ by by removing the $r_k$-th row and the $r_k$-column. Continuing this process for rows $r_{k-1},\ldots, r_1$ with end with $\det \mathcal A = \det \mathcal C$ where $ \mathcal C$ has columns $c_i = a_{j_i}$. Thus $\det \mathcal A = \det \mathcal C \ne 0$, i.e. $\operatorname{rank} \psi'(x) = n$. Now let $\sigma$ be the permutation of $\{1,\ldots,n\}$ such that $\sigma(j_i) = k + i$ for $i = 1,\ldots, n-k$ and $\sigma(r_i) = i$ for $i =1,\ldots,k$. Define $P : \mathbb R^n \to \mathbb R^n, P(x_1,\ldots,x_n) = (x_{\sigma(1)},\ldots, x_{\sigma(n)})$. This is a linear isomorphism, thus a diffeomorphism. The map $\phi = P \circ \psi$ has $\operatorname{rank} \phi'(x) = n$ and is given by
$$\phi_r(x_1,\ldots,x_n) = \begin{cases} x_r & r \in \{1,\ldots,k\} \\ F_i(x_1,\ldots,x_n) & r = k + i \end{cases}$$
Therefore $\phi^{-1}(\mathbb R^{k,n}) = \{ \xi \mid \phi(\xi) \in \mathbb R^{k,n} \} = \{\xi \mid \phi_r(\xi) = 0 \text{ for } r > k \} = \{\xi \mid F_i(\xi) = 0 \text{ for } i  \le n-k \} =  F^{-1}(0) = O_x \cap M$.

$(5) \Rightarrow (2)$: Let $h : O_x \to V$ as in $(5)$, where $h(x) = 0$. Let $i^{k,n} : \mathbb R^k \to \mathbb  R^n, i^{k,n}(x_1\ldots,x_k) = (x_1\ldots,x_k,0 \dots, 0)$ and $V_0 = (i^{k,n})^{-1}(V)$. This is an open neigborhood of $0$ in $\mathbb R^k$ and $f : V_0 \stackrel{i^{k,n}}{\to} V \stackrel{h^{-1}}{\to} O_x$ is smooth with $f(0) = x$. We have $\operatorname{rank} (i^{k,n})'(y) = k$ for all $y$, thus  $\operatorname{rank} f'(0) = k$. Clearly $f$ maps $V_0$ homeomorphically onto $O_x \cap M = f(V_0)$ which is open in $M$.

$(2) \Rightarrow (5)$: The $n \times k$ matrix $f'(0)$ has rank $k$, thus among its $n$ row vectors $b_j$ we can pick $k$ linearly independent vectors $b_{j_1},\ldots,b_{j_k}$ with $1 \le j_1 \le j_2 \le \ldots \le j_k \le n$. Write $C  = \{j_1,\ldots,j_k\}$ and $D = \{ 1, \ldots, n\} \setminus C = \{r_1, \ldots,r_{n-k}\}$ with $1 \le r_1 \le r_2 \le \ldots \le r_{n-k} \le n$. Define
$$F: V_0 \times \mathbb R^{n-k} \to \mathbb R^n, F_r(x_1,\ldots,x_n) = \begin{cases} f_r(x_1,\ldots,x_k) & r \in C \\ f_r(x_1,\ldots,x_k) + x_{k+i}  & r = r_i \in D \end{cases}$$
For $i =1, \ldots,n-k$ the $(k+i)$-th column of $\mathcal B  = F'(x)$ has the form $(0 \ldots 0 \phantom{.} 1 \phantom{.} 0 \ldots 0)^T$ where the entry $1$ is at position $r_i$. We can compute $\det \mathcal B$ by Laplace expansion along columns. As above we get $\det \mathcal B = \det \mathcal C$ where $ \mathcal C$ has rows $c_i = b_{j_i}$. Thus $\operatorname{rank} F'(x) = n$. Therefore there exist open neigborhoods $U_x$ of $x$ in $ \mathbb R^n$ and $W$ of $0$ in $V_0 \times \mathbb R^{n-k}$ such that $F(W) = U_x$ and $g = F \mid_{U_x}: W \to U_x$ is a diffeomorphism. We can write $W \cap \mathbb R^{k,n} = W_0 \times \{0\}$ with $0 \in \mathbb R^{n-k}$ and open $W_0 \subset V_0$. We get $g(W \cap \mathbb R^{k,n}) = g(W_0 \times \{0\}) = F(W_0 \times \{0\}) = f(W_0)$. Thus $g(W \cap \mathbb R^{k,n})$ is an open subset of $M$ which is clearly contained in $U_x \cap M$, but we cannot be sure that $g(W \cap \mathbb R^{k,n}) = U_x \cap M$ since points of $W \setminus \mathbb R^{k,n}$ could be mapped to $M$. Let us resolve this problem. Since $f(W_0)$ is open in $M$, each $y \in f(W_0)$ admits an open Euclidean ball $B(y)$ with center $y$ such that $B(y) \cap f(W_0) \subset f(W_0)$ and $B(y) \subset U_x$. Then $O_x = \bigcup_{y \in f(W_0)}B(y) \subset U_x$ is an open neigborhood of $x$ in $\mathbb R^n$ such that $O_x \cap M = f(W_0)$ and $V = g^{-1}(O_x)$ is an open neigborhood of $0$ in $\mathbb R^n$ such that $g(V \cap \mathbb R^{k,n}) = f(W_0) = O_x \cap M$ and $h = g^{-1} : O_x \to V$ is the desired diffeomorphism.


问:
For all sets $A, B$ and $C$ if $A\subseteq C$ and $B\cap C^{c} = \varnothing$, then $A\cup B \subseteq C$
This is the proof: For all sets $A, B$, and $C$
if $A\subseteq C$ and $B\cap C^{c} = \varnothing$, then $A\cup B \subseteq C$.

So far I've gathered some thoughts: if $B\cap C^{c} = \varnothing$, then $\varnothing\in B$ and $\varnothing\not\in C$. if $A \subseteq C$, then $\varnothing\not\in A$. So, if I'm following correctly then $\varnothing\in A\cup B$ and $A\cup B \not\subseteq C$ and the proof is false?

I'm struggling putting this into a formatted proof but I want to make sure I'm understanding it before I do so.

答: Since $B \cap C^c= \emptyset$ we know that for every $x \in B$, $x \notin C^c$. So $x \in C$. Hence $B \subseteq C$. Now, since $A,B \subseteq C$, we have that $A \cup B \subseteq C$.


问:
finite neighborhood base
My question might seem obvious but still I want to sure if the result I shall state below is true:

if the neighborhood base in each point of a space say X is finite. Then we have a discrete topology.

Many thanks and apologies in case I just stated some insanity above :)

答:
No, this is not true.  It would imply, for instance, that every finite topological space is discrete, but this is far from the case.  For a trivial example, take the trivial (or indiscrete) topology on any finite set $X$ of cardinality greater than one.  Or take the Sierpinski space, i.e., the unique two-point space (up to homeomorphism) with one open point and one closed point.

Thinking about these examples may help you formulate further conditions on your space sufficient for what you want to hold.  Hint: think about separation axioms.

Title: finite neighborhood base


问:
Centre of Mass of polygon-based Pyramid
I've been studying centres of masses for different solids and laminas in class recently, and it seems from the exercises that I have done that the centre of mass of a right regular-polygon-based pyramid of uniform density is always situated at $\frac{h}{4}$ vertically away from the base, eg for when the the base is a circle and the pyramid is a cone and for a square based pyramid, as well as a regular tetrahedron. In all the cases I am talking about, the top vertice of the pyramid is along the axis of symmetry, ie directly above the centre of the base.

I have been wondering if there is any way to prove this for the general case of any regular-polygon-based pyramid?

Thanks for your help.

答:
Yes, the centroid of an $n$-dimensional pyramid or cone is always $1/(n+1)$ of the distance along the line from the centroid of its $(n-1)$-dimensional base to its apex.

If the base is $B\subset\mathbb R^{n-1}$, the pyramid $P\subset\mathbb R^n$ with height $h$ can be parametrized as

$$P=\{(1-t)(x_1,x_2,\cdots,x_{n-1},0)+t(0,0,\cdots,0,h)\mid(x_1,x_2,\cdots,x_{n-1})\in B,\;t\in[0,1]\}.$$

That is, any $\vec y\in P$ can be written as a linear interpolation of some point $\vec x$ in the base and the apex point $h\vec e_n=(0,0,\cdots,0,h)$.

The centroid of $B$ is the average position of all points in $B$, calculated as the integral

$$\vec c_B=\frac{\int_{\vec x\in B}\vec x\,dx_1dx_2\cdots dx_{n-1}}{\int_{\vec x\in B}\,dx_1dx_2\cdots dx_{n-1}},$$

and similarly the centroid of $P$ which we want to find is

$$\vec c_P=\frac{\int_{\vec y\in P}\vec y\,dy_1dy_2\cdots dy_{n-1}dy_n}{\int_{\vec y\in P}\,dy_1dy_2\cdots dy_{n-1}dy_n}.$$

We need to relate the volume element of $P$ to the volume element of $B$, using the Jacobian of the coordinate system $(x_1,x_2,\cdots,x_{n-1},t)\mapsto(y_1,y_2,\cdots,y_{n-1},y_n)$:

$$\vec y=(1-t)\vec x+th\vec e_n$$

$$\frac{\partial\vec y}{\partial x_1}=(1-t)\vec e_1,\quad\frac{\partial\vec y}{\partial x_2}=(1-t)\vec e_2,\quad\cdots,\quad\frac{\partial\vec y}{\partial x_{n-1}}=(1-t)\vec e_
{n-1},\quad\frac{\partial\vec y}{\partial t}=h\vec e_n-\vec x$$

$$J=\begin{bmatrix}(1-t)&0&0&\cdots&0&-x_1\\0&(1-t)&0&\cdots&0&-x_2\\0&0&(1-t)&\cdots&0&-x_3\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\0&0&0&\cdots&(1-t)&-x_{n-1}\\0&0&0&\cdots&0&h\end{bmatrix}$$

$$\det J=(1-t)^{n-1}h$$

$$dy_1dy_2\cdots dy_{n-1}dy_n=(1-t)^{n-1}h\,dx_1dx_2\cdots dx_{n-1}dt.$$

Integrating this immediately gives the pyramid's volume $|P|=\frac1n|B|h$. Proceeding to calculate the centroid,

$$\vec c_P=\frac{1}{|P|}\int_{t\in[0,1]}\int_{\vec x\in B}\big((1-t)\vec x+th\vec e_n\big)(1-t)^{n-1}h\,dx_1dx_2\cdots dx_{n-1}dt$$

$$=\frac{1}{|P|}\int_{t\in[0,1]}\bigg((1-t)^n\int_{\vec x\in B}\vec x\,dx_1dx_2\cdots dx_{n-1}+t(1-t)^{n-1}h\vec e_n\int_{\vec x\in B}\,dx_1dx_2\cdots dx_{n-1}\bigg)h\,dt$$

$$=\frac{1}{|P|}\int_{t\in[0,1]}\bigg((1-t)^n|B|\vec c_B+t(1-t)^{n-1}h\vec e_n|B|\bigg)h\,dt$$

$$=\frac{|B|h}{|P|}\bigg(\frac{1}{n+1}\vec c_B+\frac{1}{n(n+1)}h\vec e_n\bigg)$$

$$=\frac{n}{n+1}\vec c_B+\frac{1}{n+1}h\vec e_n.$$

So we can write $\vec c_P=(1-t)\vec c_B+th\vec e_n$ where $t=1/(n+1)$.

Title: Centre of Mass of polygon-based Pyramid


问:
Method/approach to show given set is closed
I have to show that the domain defined by the half unit circle: $\left \{ \left ( x,y \right )\in \mathbb{R}^2: x^2+y^2\leq 1, x\geq 0 \right \}$

for the function $f:D\rightarrow \mathbb{R}$ is closed (the function is $f(x,y)=2xy^2-2x^2$), so that I can argue the function has a min/max value. I have shown it is bounded and continuous. I just can not seem to find a method or way to “formally” show it is closed? I get the intersection of 2 closed sets is closed but how would one ACTUALLY show these sets are closed?

答:
Notice $D=A \cap B$ where $A=\{(x,y); x^2 +y^2 \leq 1\}$ and $B=\{(x,y); x \geq 0\}$. Let's show that $B^c=\{(x,y); x < 0\}$ and $A^c=\{(x,y); x^2 +y^2 > 1\}$ are open. Notice that given $(x,y) \in B^c$ we know that $x<0$. By choosing $\delta = \frac{|x|}{2}$ we get
$$
B((x,y),\delta) \subset B^c
$$
where $B((x,y),\delta)$ is the ball centered at $(x,y)$ with radius $\delta$. So we can conclude that $B^c$ is open. Hence $B$ is closed. Try to do something similar with $A^c$. Then you will have that $D$ is the intersection of closed sets as you want.


问:
maximum number of edges to be removed to possess a property
I am working on a problem. We know that on squaring a cycle, degree of every vertex is 4. For squares of cycles, we know if we delete any arbitrary edge then still eccentricity is same for all vertices. And if we delete 3 edges incident on a single vertex, it loses its property that eccentricity is same for all vertices, because eccentricity is not same for those graphs having a vertex of degree1. How to find out the maximum number of edges to be deleted so that eccentricity is still same.  Any idea or suggestion will be helpful. Thanks for your help.</p>

答:
The square $G$ of a cycle graph of length $n$ has vertices $0,1,\ldots, n-1$ and an edge between $a$ and $b$ iff $a-b\equiv -2, -1, 1, \text{ or }2\pmod n$. Note that this implies that the claim that $\rho(a)=4$ for all vertices holds only if $n>4$. Therefore, in what follows, we shall assume that $n>4$.
Let $F(n)$ be the minimum number of edges that can be removed such that the same-eccentricity-property of $G$ is destroyed.

The distance in $G$ from vertex $0$ to vertex $k$ is quite obviously $d(0,k)=\min\{\lceil\frac k2\rceil,\lceil\frac {n-k}2\rceil\}$ and hence the eccentricity of $0$ is $\epsilon(0)=\left\lceil\frac{\lfloor \frac {n}2\rfloor}2\right\rceil=\lfloor\frac{n+2}4\rfloor$ (and by symmetry for all vertices).
We observe the following about shortest paths from $0$ to $k$:

All steps go clockwise or all go counterclockwise. This is because two consecutive steps in opposite direction either cancel or can be replaced by a single step.

If $\lceil \frac k2\rceil=\lceil \frac {n-k}2\rceil$, shortest paths of both clockwise and anticlockwise orientation exist.

Lemma 0. If $n\not\equiv 1\pmod 4$, then $F(n)>1$.

Proof: Let $G^\star$ be any graph obtained from $G$ by removing one edge.
Since each edge in $G$ is part of a triangle, $d^\star(v,w)\le d(v,w)+1$. Therefore, eccentricity can only change if the distance to the farthest vertices grows. For $v=0$, those are as follows:

If $n=4m-2$: $w=2m$ with a path of length $m$ clockwise and counterclockwise

If $n=4m$: $w=2m$ with as path of length $m$ clockwise and counterclockwise; $w=2m\pm1$ with a path beginning and a path ending with an edge of length $1$

If $n=4m-1$: $w=2m$ with a path of length $m$ clockwise (all steps of length $2$) and several paths counterclockwise (with one step of length $1$); $w=2m+1$ similarly.

In all cases, there are two edge-disjoint paths of the required length, hence the distance does not change when removing a single edge. $_\square$

Lemma 1. If $n\equiv 1\pmod 4$, then $F(n)=1$.

Proof:
Assume $n=4m+1$ (so that $\epsilon(v)=m$) and let $G'$ be the graph $G$ with edge $(0, 2)$ removed.
Clearly, $d'(1,v)=d(1,v)$ for all $v$ and hence $\epsilon'(1)=\epsilon(1)$.
The only path $0\stackrel 2\to2\stackrel 2\to\ldots\stackrel 2\to2m$ of length $m$ from $0$ to $2m$ does not exist in $G'$, hence $$\epsilon'(0)\ge d'(0,2m)>m=\epsilon(1).$$
Removing a single edge can destroy the same-eccentricity-property.
$_\square$

Lemma 2. If $n\equiv 3\pmod 4$, then $F(n)=2$.

Proof:
Let $n=4m-1$ (so that $\epsilon(v)=m$ for all $v$) and let $G''$ be $G$ with edges $(0,1)$ and $(0,2)$ removed.
Then $$\epsilon''(0)\ge d''(0,2m-2)\ge \min\{d(n-1,2m-2),d(n-2,2m-2)\}+1=m+1$$ because any path from $0$ must have $n-1$ or $n-2$ as next node.
On the other hand, $d''(1,v)=d(1,v)$ unless all shortest $G$-paths from $1$ to $v$ contain either $(0,1)$ or $(0,2)$. The latter is never the case and the former only if $v=0$ (but that case does not matter as $d''(1,0)=2\le m$) as otherwise the shortest path continues $1\stackrel 1\to 0\stackrel 2\to n-2$ and can be replaced with $1\stackrel 2\to n-1\stackrel1\to n-2$. Hence $\epsilon''(1)=\epsilon(1)=m$. $_\square$

Lemma 3. If $n\equiv 0\pmod 4$, then $F(n)=2$.

Proof:
Let $n=4m$ (so that $\epsilon(v)=m$) and again let $G''$ be $G$ with edges $(0,1)$ and $(0,2)$ removed.
Then $$\epsilon''(0)\ge d''(0,2m-1)\ge \min\{d(n-1,2m-1),d(n-2,2m-1)\}+1=m+1$$
whereas just as above $\epsilon''(1)=\epsilon(1)$.
 $_\square$

Lemma 4. If $n\equiv 2\pmod 4$, then $F(n)=3$.

Proof:
Let $n=4m-2$ (so $\epsilon(v)=m$) with $m\ge 2$ and let $G^\star$ be any graph obtained by removing two edges from $G$. We will show that $d^\star(0,v)\le m$ for $1\le v\le 2m-1$. Then by symmetry we will have $\epsilon^\star(v)=m$ for all $v$.

For $v=2m-1$, note that there are four edge-disjoint paths of length $m$: $0\stackrel 1\to 1\stackrel2\to\ldots\stackrel2\to 2m-1$, $0\stackrel 2\to 2\stackrel2\to\ldots\stackrel2\to 2m-2\stackrel1\to 2m-1$, ans similarly in negative direction. At most two of these can be destroyed by the edge removal, hence $d^\star(0,v)=m$.

For $v=2m-2$, we have edge-disjoint paths $0\stackrel2\to n-2\stackrel2\to\ldots\stackrel2 2m-2$, $0\stackrel2\to2\stackrel2\to\ldots\stackrel2\to 2m-2$ and $0\stackrel 1\to1\stackrel2\to\ldots\stackrel1\to 2m-2$ of lengths $\le m$. Again, one must survive the edge removal, $d^\star(0,v)\le m$.

For $2<v<2m-2$ odd, we have two edge-disjoint paths $0\stackrel 1\to 1\stackrel 2\to\ldots\stackrel2\to v$ and $0\stackrel 2\to 2\stackrel 2\to\ldots\stackrel1\to v$ of length $<m$. Unless each of these paths contains exactly one of the removed edges, we are done. If $(0,1)$ is a removed edge, then $0\stackrel 1n-1\to 2\stackrel 1\to 1\stackrel 2\to\ldots\stackrel2\to v$ has length $m$ (note that $(1,2)\ne(v-1,v)$ and we are done. Similarly, we are done if $(v-1,v)$ is a removed edge. Therefore, we may assume that in each of the two paths, an edge $(k,k+2)$ is removed and that edges $(k,k+1)$ and $(k+1,k+2)$ are both present in $G^\star$ so that we obtain a path of length $\le m$.

For $2\le v<2m-2$ even, we have two edge-disjoint paths $0\stackrel 1\to1\stackrel 2\to\ldots\stackrel1\to v$ and $0\stackrel 22\stackrel 2\to\ldots\stackrel2\to v$ of length $<m$. Again we may assume that exactly one edge of each path is missing. Again, if $(0,1)$ is removed, we can replace it with $0\stackrel 1n-1\stackrel 21$ andsimilarly if $(v-1,v)$ is missing. Again we conclude that in each of the two paths, an edge $(k,k+2)$ is removed and that edges $(k,k+1)$ and $(k+1,k+2)$ are both present in $G^\star$ so that we obtain a path of length $\le m$.

For the remaining case $v=1$, note that we have three edge-disjoint paths $0\stackrel 1\to 1$, $0\stackrel 2\to 2\stackrel 1\to 1$ and $0\stackrel 1\to n -1\stackrel 2\to 1$ of length $\le 2\le m$, at least one of which is present in $G^\star$. Together with your own result about three edges, the claim of the lemma follows.
$_\square$

In summary, we have therefore

Theorem. Let $n>4$. Then $$F(n)=\begin{cases}2 & \text{if }n\equiv 0\pmod 4\\1 & \text{if }n\equiv 1\pmod 4\\3 & \text{if }n\equiv 2\pmod 4\\2 & \text{if }n\equiv 3\pmod 4\\\end{cases}$$

Remark: Note the degenerate cases $F(4)=1$ and $F(3)=1$.


问:
Intersection of nested open sets in compact Hausdorff space
Let $U$ be an open subset of compact Hausdorff space $X$. Choose a non-empty subset $U_1$ in $X$ with $\overline{U}_1\subseteq U$. Repeating this construction without end, we can then find a sequence of open non-empty sets $\{U_n\}_{n\in\mathbb{N}}$ in $X$ with $U_{n+1}\subseteq \overline{U}_{n+1}\subseteq U_n$.

$X$ is a compact Hausdorff space but it may be not metrizable. Can I say that $\bigcap _{n\in\mathbb{N}}U_n\neq \emptyset$?

Pease help me to know it.

答:
Yes, we have $D = \bigcap _{n\in\mathbb{N}}U_n \ne \emptyset$.

In fact, since $U_{n+1}\subset \overline{U}_{n+1}\subset U_n$, we get
$$D  = \bigcap _{n\in\mathbb{N}} \overline{U}_n .$$
The family $\{ \overline{U}_n \}$  clearly has the finite intersection property which means that each finite intersection of members is non-empty. It is well-known that a space $X$ is compact iff any family of closed subsets which has the finite intersection property has a non-empty intersection.


问:
If $f\in L^1$, then $F(x):=\int_0^x{f(s)ds}$ is also in $L^1$
Let $\Omega=]0,1[$ and $f\in L^1(\Omega)$, show that

$$F(x):=\int_0^x{f(s)ds}, \forall x \in\Omega$$ is also in $L^1(\Omega).$

I was working with this exercise and would appreciate some ideas/ways to solve this.

My idea:

Notice: $$\int_0^1{\lvert f\rvert} < \infty$$
Then $\forall x\in\Omega$:$$\int_0^x{\lvert f(s)\rvert ds} < \infty$$

We can apply Fubini-Tonelli for:
$$\int_0^1 \left( \int_0^x{\lvert f(s)\rvert ds}\right) dx $$

which is where I got stuck. Thanks.

答:
Hints: show $F$ is continuous by noting that

$1).\ \mathbb 1_{\{|f| > \lambda\}}|f| \le |f|$ and so $\underset{\lambda \to\infty}\lim\int_{\{|f| > \lambda\}}|f|\ d\mu = 0$

$2).\ \int_{x_0}^{x_0+h}|f|\ d\mu = \int_{[x_0,x_0+h] \cap \{|f| > \lambda\}}|f|\ d\mu + \int_{[x_0,x_0+h] \cap \{|f| \le \lambda\}}|f|\ d\mu$

$3).\ $ With $\delta <\frac{\epsilon}{2\lambda}$, choose $h$ so that $m([x_0,x_0+h])<\delta$

$4).\ $ Combine $2).$ and $3).$


问:
Having two points of a square and only a compass, how to find the remaining two?
I remember being presented a mathematical puzzle some years back that I still can't solve. The problem is defined as follows:

We have two points on a plane, and using only a compass, how do we find other two points, so that all four of them would be vertices of a square?

I'm not sure whether the first two points were supposed to be vertices of the same edge of a square or not, so solutions to both variants are welcome.

答:
There's an easier solution with a collapsible compass.
Let the final square side (distance between two initial points) be equal to 1.

First, draw three small circles with the radius of 1

Then draw tree large circles with the radius of sqrt3.

Now all you need is to find sqrt2. That will be outer crossing of the large circles. Draw two medium circles centered in your initial points.

The crossing of the medium circles with the first two small ones are the top points you need.

See diagram


问:
Proving that if $n$ is odd and $\gcd(m, n) = 1$, then $\gcd(2m + n, 2n) = 1$
I've been trying to crack this one for the last little while. I've tried a few approaches, but none have bore any fruit.

Let $n > 0$ be an odd integer. Prove that if $\gcd(m, n) = 1$, then $\gcd(2m + n, 2n) = 1$.

答:
It can easily be deduced that $d(=gcd(2m+n,2n))$ will be odd because if it is not then $2|(2m+n) \Rightarrow 2|n$ which is not true.

Now ($d|2n \Rightarrow d|n$ and $d|(2m+n) \Rightarrow d|m$) $\Rightarrow d|gcd(m,n)\Rightarrow d|1\Rightarrow d=1$


答: To complete your argument note that (by Tonnelli's Theorem)  $\int_0^{1}\int_0^{1}\chi_{(0,x)}(s) |f(s)|dsdx=\int_0^{1}\int_0^{1}\chi_{(s,1)}(x) |f(s)|dxds$ because $\chi_{(0,x)}(s)=\chi_{(s,1)}(x)$ for all $x$ and $s$. Hence $\int_0^{1}\int_0^{1}\chi_{(0,x)}(s) |f(s)|dsdx= \int_0^{1} (1-s)|f(s)|ds \leq \int_0^{1} |f(s)| ds <\infty$.

Title: If $f\in L^1$, then $F(x):=\int_0^x{f(s)ds}$ is also in $L^1$

Body:
Let $\Omega=]0,1[$ and $f\in L^1(\Omega)$, show that

$$F(x):=\int_0^x{f(s)ds}, \forall x \in\Omega$$ is also in $L^1(\Omega).$

I was working with this exercise and would appreciate some ideas/ways to solve this.

My idea:

Notice: $$\int_0^1{\lvert f\rvert} < \infty$$
Then $\forall x\in\Omega$:$$\int_0^x{\lvert f(s)\rvert ds} < \infty$$

We can apply Fubini-Tonelli for:
$$\int_0^1 \left( \int_0^x{\lvert f(s)\rvert ds}\right) dx $$

which is where I got stuck. Thanks.


问:
Is $\left\{z\in\Bbb C\;:\;\left|\frac{\epsilon}z-a\right|<r\right\}$ a circle?
Let us fix $a=se^{i\psi}\in\Bbb C,\;r>0,\epsilon>0$.

I want to describe the set
$$
A:=\left\{z\in\Bbb C\;:\;\left|\frac{\epsilon}z-a\right|<r\right\}\;\;.
$$

First I notice that
$$
\frac{\epsilon}z=a\;\;\Longleftrightarrow z=\frac{\epsilon}{s}e^{-i\psi}.
$$
Call it $z_0$.
Now, if we move in $A$, on the line of complex numbers of argument $-\psi$, the most distant elements from $z_0$ are $z_{\pm}:=\left(\frac\epsilon s\pm r\right)e^{-i\psi}$ (which are in $\partial A$ to be precise), so it follows that
$$
\lambda e^{-i\psi}\in A,\;\;\lambda\in\left(\frac\epsilon s-r,\frac\epsilon s+r\right).
$$
Moreover, for every such $\lambda$, there exists $g(\lambda)>0$ such that
$$
\lambda e^{-i\phi}\in A\;\;\Longleftrightarrow \phi\in\left(\psi-g(\lambda),\psi+g(\lambda)\right)=:I_{\lambda}\;.
$$
It is clear that:

-$g$ is continuous (and I'd say smooth)

-$g(\lambda)\to0^+$ as $\lambda\to\frac\epsilon s\pm r$

-it reaches its maximum at the midpoint $\lambda_0=\frac\epsilon s$

-it's symmetric with respect to $\lambda_0$

Hence $A$ can be described as follows:

$$
A=\left\{\lambda e^{-i\phi}\;:\;\lambda\in\left(\frac\epsilon s-r,\frac\epsilon s+r\right),\;
\phi\in\left(\psi-g(\lambda),\psi+g(\lambda)\right)\right\}\;\;.
$$

My suspect is that $g$ increases till $\lambda_0$ and then decreases to $0$ in a way that the surface spanned is exactly a circle, namely
$$
A=\left\{\left|z-\frac\epsilon a\right|<r\right\}\;.
$$
What can I do to get more information on $g$ to prove/disprove this last equality?

答:
$W = \{w \in \mathbb C: |w - a| = r\}$ is the circle of radius $r$ centred at $a$.  It is the image of
$Z = \{z \in \overline{\mathbb C}: |\epsilon/z - a| = r\}$ under the inversion $f: z \to  \epsilon/z$, where $\overline{\mathbb C}$ is the Riemann sphere (the extended complex plane).
That being a Möbius transformation, it takes circles and lines into circles and lines.  To make sure it is a circle and not a line, we just need to make sure it doesn't contain the point at $\infty$, i.e. that $|a| \ne r$.  Now $A = \{z \in \mathbb C: |\epsilon/z - a| < r\}$ is either the inside or the outside of the circle $Z$.  To check which it is, we just need to check what happens to $\infty$ under the transformation. What we need for it to be the inside of the circle is that it doesn't contain a deleted neighbourhood of $\infty$, i.e. that $|a| > r$.


问:
Confusion about writing $Inf$ as a $\Pi_2$ set
I would express the fact that $p$ lies in the set of programs with infinite domain $Inf$ as follows:

$$p\in Inf\iff\forall x\exists y > x \exists z T(p,y,z)\\ \iff \forall x\exists y(y > x \to \exists z T(p,y,z))\\ \iff \forall x\exists z\exists y(y > x\to T(p,y,z)) $$

but I've read somewhere that this property is expressed as $$p\in Inf\iff \forall x \exists z\exists y (y
 > x \land T(p,y,z))$$
and I believe these expressions aren't equivalent. Did I express this incorrectly then? I don't see anything wrong with my (first) expression.

答:
You did express it incorrectly. The issue is in treating the bounded quantifiers - "$\forall$" and "$\exists$" behave quite differently:

"$\forall a<b(\varphi)$" is an abbreviation for "$\forall a(a<b\rightarrow\varphi)$."

"$\exists a<b(\varphi)$" is an abbreviation for "$\exists a(a<b\wedge\varphi)$."

Note that there is not an obvious notational "duality" here. It is still true however that the two  bounded quantifiers are dual to each other in the sense that $$\neg\exists a<b\neg(\varphi) \quad\equiv\quad \forall a<b(\varphi)$$ and similarly $$\neg \forall a<b\neg(\varphi) \quad\equiv\quad \exists a<b(\varphi).$$ So this is a case where the logical notation we're used to actually makes it a little harder to remember what the abbreviations mean.


问:
Determine no of combinations for cutting stock algorithm
I have to buy $n$ wooden logs of size 2000 each, from which I have to cut different pieces of smaller size say:

```<code>255*10
750*7
550*13
</code>```

In a manner that cutting will cause minimum no of purchases ($n$) and minimum wastage.

I found a similar problem in wikipedia (click this link) which gives an example(see in the link) and says:

"There are 308 possible patterns for this small instance. The optimal answer requires 73 master rolls and has 0.401% waste"

I want to know how it calculated the no of combinations to be 308.

答:
I had a misunderstanding. I thought 308 is the no of combinations for making all rolls as given in data and one of the 308 combination is the optimal answer given there, but now I have understood that 308 is the no of combinations for making use of the first 5600 width roll. Example

```<code>1380
1380+1380
1380+1380+1380
1380+1380+1380+1380
1380+1380+1520
.
..
</code>```

and so on, 308 combinations are possible.

I verified it by making a java program to calculate combinations in this manner which gave result 308.

```<code>class Pappu
{
  static int total,comb[],max[],count=0;
  public static void main(String ...s)
  {
    int maxlen=5600;
    int arr[]={2200,2150,2140,2100,2050,2000,1930,1880,1820,1710,1560,1520,1380};
    int qty[]={20,18,16,14,12,10,20,18,18,14,12,25,22};
    boolean chaloo=true;
    int sum=0;
    total=arr.length;
    max=new int[total];
    comb=new int[total];
    for(int i=0;i<total;i++)  //calculating upper bound of combination
    {
      max[i]=maxlen/arr[i];
    }
    while(chaloo)
    {
      combinations();
      for(int i=0;i<total;i++)
        sum+=arr[i]*comb[i];
      if(sum<=maxlen)
        count++;    //counting only those combination which can be cut from size under 5600
      sum=0;
      for(int i=0;i<total;i++)
      {
        if(comb[i]!=max[i])
        {
          chaloo=true;
          break;
        }
        chaloo=false;
      }
    }
    System.out.println(count);
  }
      /* combination generated are of form
    0000000000001
    0000000000002
    0000000000003
    .....
    0000000000010
    0000000000011
    .....
    till upeer bound of max[]
    */
  static void combinations() //combination generator
  {
      for(int i=total-1;;)
      {
        if(comb[i]!=max[i])
        {
          comb[i]++;
          break;
        }
        else
        {
          if(i==0 && comb[0]!=max[0])
            i=total-1;
          else
          {
            comb[i]=0;
            i--;
          }
        }
      }
  }
}
</code>```

Body:
I had a misunderstanding. I thought 308 is the no of combinations for making all rolls as given in data and one of the 308 combination is the optimal answer given there, but now I have understood that 308 is the no of combinations for making use of the first 5600 width roll. Example

1380
1380+1380
1380+1380+1380
1380+1380+1380+1380
1380+1380+1520
.
..

and so on, 308 combinations are possible.

I verified it by making a java program to calculate combinations in this manner which gave result 308.

class Pappu
{
  static int total,comb[],max[],count=0;
  public static void main(String ...s)
  {
    int maxlen=5600;
    int arr[]={2200,2150,2140,2100,2050,2000,1930,1880,1820,1710,1560,1520,1380};
    int qty[]={20,18,16,14,12,10,20,18,18,14,12,25,22};
    boolean chaloo=true;
    int sum=0;
    total=arr.length;
    max=new int[total];
    comb=new int[total];
    for(int i=0;i<total;i++)  //calculating upper bound of combination
    {
      max[i]=maxlen/arr[i];
    }
    while(chaloo)
    {
      combinations();
      for(int i=0;i<total;i++)
        sum+=arr[i]*comb[i];
      if(sum<=maxlen)
        count++;    //counting only those combination which can be cut from size under 5600
      sum=0;
      for(int i=0;i<total;i++)
      {
        if(comb[i]!=max[i])
        {
          chaloo=true;
          break;
        }
        chaloo=false;
      }
    }
    System.out.println(count);
  }
      /* combination generated are of form
    0000000000001
    0000000000002
    0000000000003
    .....
    0000000000010
    0000000000011
    .....
    till upeer bound of max[]
    */
  static void combinations() //combination generator
  {
      for(int i=total-1;;)
      {
        if(comb[i]!=max[i])
        {
          comb[i]++;
          break;
        }
        else
        {
          if(i==0 && comb[0]!=max[0])
            i=total-1;
          else
          {
            comb[i]=0;
            i--;
          }
        }
      }
  }
}


问:
Does $x_k$ identically distributed with finite mean imply $x_k/k$ converges to 0 $a.s.$?
I am not sure whether the following statement is true. Let $x_k$ be identically distributed, and only assumed to have finite mean. Can we conclude that $x_k/k$ converges a.s.? Clearly it converges in probability. And if we compute
$$
 P(|x_k|\geq k\epsilon)\leq \frac{E|x_k|}{k\epsilon}$$

However, since we only assume finite mean, it is not sufficient to conclude the almost everywhere convergence. I can come up with counterexamples when $x_i$ are not identically distributed. But not for the identically distributed case. Does anyone have any idea about this?

Thanks in advance.

答:
Yes, it is true. I will use $X_k$ instead of $x_k$. To show $X_k/k\to 0$ a.s, it suffices to show $\sum_{k=1}^\infty P(|X_k/k|>\epsilon)<\infty$, for all $\epsilon>0$.
$$
\sum_{k=1}^\infty P(|X_k/k|>\epsilon)=\sum_{k=1}^\infty P(|X_1/\epsilon|>k)\le \int_0^\infty P(|X_1/\epsilon|>t)\,dt=E|X_1/\epsilon|
<\infty$$
In fact, you can prove the converse, that $X_k/k\to 0$ a.s. implies $E|X_1|<\infty$, in a similar fashion.