问:
What does the term number / probability refer in those graphs
I'm trying to understand one graph presented in our online statistics class. I understand how the numbers are calculated, I cannot understand what the number / probability is referring to, I tried replicating the same experiment and I cannot understand how the numbers in range 1-5 were received for 10 numbers, or the numbers from 1 to 40 for mean of 100 numbers.

I understand that the bars show that the mean is more likely to be in center (around 0.5), but I cannot understand what the number of their heigh exactly refers to.

Here is uploaded image of the graphs, they are received after the professor sampled N points uniformly from the range [0, 1) and calculated the mean 1000 times.

Thanks in advance.

答:
Let $A_{10}$ be the mean of $n=10$ observations from the standard
uniform distribution $\mathsf{Unif}(0,1).$ Sampled using R.

```<code>set.seed(220)
a.10 = replicate(1000, mean(runif(10)))
summary(a.10);  sd(a.10)
    Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
 0.2245  0.4410  0.4967  0.5004  0.5612  0.8489
[1] 0.08972384  # aprx 0.09129
hist(a.10, prob=T, xlim=c(0,1), col="skyblue2")
curve(dnorm(x, mean(a.10), sd(a.10)), add=T, col="orange", lwd = 2)
</code>```

We have found a thousand averages $A_{10}.$ Here $E(A_{10}) = 0.5.$ The standard deviation of the population
$\mathsf{Unif}(0,1)$ is $\sigma = \sqrt{1/12} = 0.28868.$ So $SD(A_{10}) = \sigma/\sqrt{10} = 0.09129.$ The mean and the standard deviation of the sample of a thousand averages matches these values very well.

For uniform data, the central limit
converges to normal very fast, so $A_{10}\stackrel{aprx}{\sim}\mathsf{Norm}(\mu=.5,\sigma = 0.09129).$ This is shown by the reasonably good fit of the orange normal
density curve to the histogram.

By contrast, if we look at averages $A_{100}$ of samples
of size $n = 100$ observations from $\mathsf{Unif}(0,1),$
we get the following results.

```<code>set.seed(221)
a.100 = replicate(1000, mean(runif(100)))
summary(a.100);  sd(a.100)
  Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
0.4129  0.4801  0.4995  0.4996  0.5176  0.5919
[1] 0.02856333

hist(a.100, prob=T, xlim=c(0,1), col="skyblue2")
 curve(dnorm(x, mean(a.100), sd(a.100)), add=T, col="orange", lwd = 2)
</code>```

Notes on plotting histograms: (1) Even though all of the one thousand averages $A_{100}$ happen to lie in $(.4,.6),$
I have maintained the interval $(0,1)$ on the x-axis of the histogram for easier comparison with the previous histogram.
As the sample size $n$ increases, the variability of the averages
of $n$ decreases.

(2) In the first histogram, look at the 5th bar with interval $(.40,.45]$ of width $w = 0.05.$ This interval contains $158$ of the $1000$ averages $A_{10},$ which is $0.158$ of the total.
So this bar has area $a = 0.158$ and width $w = 0.05$ so it's
height called 'density' is $h = 0.158/0.05 = 3.16,$ which you
can compare with the scale on the vertical axis. That's how
a density histogram is made.

I think the word density may
be the easiest to use, but it might be called something like 'relative frequency per unit width'. In a real application, the
horizontal axis might be heights, weights or dollar incomes of
people; then 'unit width' might be replaced by one of the units 'inch', 'cm', 'lb', 'kg', 'dollar', 'euro', etc.

Both of my histograms use a vertical 'density' scale (so that the
total area of all bars is $1).$ That makes it possible to
plot normal density functions on the same axes.

(3) You can compare my simulations and histograms with the second and third of the panels of the figure you posted
in your Questions.

Body:
Let $A_{10}$ be the mean of $n=10$ observations from the standard
uniform distribution $\mathsf{Unif}(0,1).$ Sampled using R.

set.seed(220)
a.10 = replicate(1000, mean(runif(10)))
summary(a.10);  sd(a.10)
    Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
 0.2245  0.4410  0.4967  0.5004  0.5612  0.8489
[1] 0.08972384  # aprx 0.09129
hist(a.10, prob=T, xlim=c(0,1), col="skyblue2")
curve(dnorm(x, mean(a.10), sd(a.10)), add=T, col="orange", lwd = 2)

We have found a thousand averages $A_{10}.$ Here $E(A_{10}) = 0.5.$ The standard deviation of the population
$\mathsf{Unif}(0,1)$ is $\sigma = \sqrt{1/12} = 0.28868.$ So $SD(A_{10}) = \sigma/\sqrt{10} = 0.09129.$ The mean and the standard deviation of the sample of a thousand averages matches these values very well.

For uniform data, the central limit
converges to normal very fast, so $A_{10}\stackrel{aprx}{\sim}\mathsf{Norm}(\mu=.5,\sigma = 0.09129).$ This is shown by the reasonably good fit of the orange normal
density curve to the histogram.

By contrast, if we look at averages $A_{100}$ of samples
of size $n = 100$ observations from $\mathsf{Unif}(0,1),$
we get the following results.

set.seed(221)
a.100 = replicate(1000, mean(runif(100)))
summary(a.100);  sd(a.100)
  Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
0.4129  0.4801  0.4995  0.4996  0.5176  0.5919
[1] 0.02856333

hist(a.100, prob=T, xlim=c(0,1), col="skyblue2")
 curve(dnorm(x, mean(a.100), sd(a.100)), add=T, col="orange", lwd = 2)

Notes on plotting histograms: (1) Even though all of the one thousand averages $A_{100}$ happen to lie in $(.4,.6),$
I have maintained the interval $(0,1)$ on the x-axis of the histogram for easier comparison with the previous histogram.
As the sample size $n$ increases, the variability of the averages
of $n$ decreases.

(2) In the first histogram, look at the 5th bar with interval $(.40,.45]$ of width $w = 0.05.$ This interval contains $158$ of the $1000$ averages $A_{10},$ which is $0.158$ of the total.
So this bar has area $a = 0.158$ and width $w = 0.05$ so it's
height called 'density' is $h = 0.158/0.05 = 3.16,$ which you
can compare with the scale on the vertical axis. That's how
a density histogram is made.

I think the word density may
be the easiest to use, but it might be called something like 'relative frequency per unit width'. In a real application, the
horizontal axis might be heights, weights or dollar incomes of
people; then 'unit width' might be replaced by one of the units 'inch', 'cm', 'lb', 'kg', 'dollar', 'euro', etc.

Both of my histograms use a vertical 'density' scale (so that the
total area of all bars is $1).$ That makes it possible to
plot normal density functions on the same axes.

(3) You can compare my simulations and histograms with the second and third of the panels of the figure you posted
in your Questions.


问:
Asymptotic running time for following recurrence function
What method should I use to find the running time of the recurrence function:

$$T(n)=T(n/4)+T(3n/4)+\theta(n)$$

I've tried to solve this question by guess-and-check.
I assumed that the total size of on each level of the tree is less than $n$, so I guessed that $f(n)=n$ will dominate.

How should I go about this?

答:
You will get some intuition from looking at the case 2 example in [1]. Since your first guess was $n$, consider $g(n)=T(n)/n$. This satisfies
$$g(n)=\frac{1}{4}g(n/4)+\frac{3}{4}g(3n/4)+\Theta(1) \,.$$
Let's ignore the implicit constant and write this as an average:
$$g(n)=\frac{1}{4}[g(n/4)+1]+\frac{3}{4}[g(3n/4)+1]  \,.$$
Replace every term of the form $g(k)+1$ on the RHS by the average
$$\frac{1}{4}[g(k/4)+2]+\frac{3}{4}[g(3n/4)+2]  \,.$$
Iterate this for every $k>100$ until you express $g(n)$ as an average of exponentially many terms of the form $g(j)+\ell$, where $j \in [25,100]$ and $\ell$ is the number of iterations needed to get from $n$ to $j$. Clearly all these different values of $\ell$ will be of order $\Theta(\log n)$, so we conclude that $g(n)=\Theta(\log n)$ and $T(n)=\Theta(n\log n)$.
Once you know the right order it is easy to verify.

[1] https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)

ContentLicense: CC BY-SA 4.0


问:
Determinant Expression
How I will be able to found any expression for the determinant of the matrix $R^{N\times N}$ wiht entries belong $\mathbb{R} $, if $R_{ij}=\dfrac{2}{N}-\delta_{ij}$?</p>

答:
I assume that $N$ is the size of the matrix, if it is not, the solution can be adapted easily.

Your matrix is

$$R= \begin{pmatrix}
\frac{2}{N}-1 & \frac{2}{N} & \frac{2}{N} & ..&\frac{2}{N} \\
\frac{2}{N} & \frac{2}{N}-1 & \frac{2}{N} & ..&\frac{2}{N} \\
\frac{2}{N} & \frac{2}{N} & \frac{2}{N}-1 & ..&\frac{2}{N} \\
...&...&...&...&... \\
\frac{2}{N} & \frac{2}{N} & \frac{2}{N} & ..&\frac{2}{N}-1 \\
\end{pmatrix}$$

Here is a simple solution if you know eigenvaleues. $R+I$ has rank $1$, which means that $\lambda=-1$ is eigenvalue of multiplicity at least $n-1$.

Also, the columns of $R-I$ add to $0$, thus $\lambda=1$ is also an eigenvalue of $R$.

Thus

$$\det(R)=(-1)^{n-1}\cdot 1 \,.$$

If you don't  know eigenvalues, add all rows to first one to get

$$\det(R)= \det \begin{pmatrix}
1 & 1 & 1 & ..&1 \\
\frac{2}{N} & \frac{2}{N}-1 & \frac{2}{N} & ..&\frac{2}{N} \\
\frac{2}{N} & \frac{2}{N} & \frac{2}{N}-1 & ..&\frac{2}{N} \\
...&...&...&...&... \\
\frac{2}{N} & \frac{2}{N} & \frac{2}{N} & ..&\frac{2}{N}-1 \\
\end{pmatrix}$$

now subtract $\frac{2}{N}$ times first row from all other rows to get:

$$\det(R)= \det \begin{pmatrix}
1 & 1 & 1 & ..&1 \\
0 & -1 & 0 & ..&0 \\
0 & 0 & -1 & ..&0 \\
...&...&...&...&... \\
0 & 0 & 0 & ..&-1 \\
\end{pmatrix}=(-1)^{n-1}$$

ContentLicense: CC BY-SA 3.0

Title: Determinant Expression


问:
Let $a,b,c$ be positive integers such that $a^3+b^3=2^c.$ Show that $a=b$.

Let $a,b,c$ be positive integers such that $$a^3+b^3=2^c.$$ Show that $a=b$.

I have that $$a^3+b^3=(a+b)(a^2-ab+b^2)=2^c =2^x\cdot2^y$$ now it can only be that $a$ and $b$ are both odd or even since they sum to an even number. Thus if $a$ and $b$ are both odd I have that $a^2$ is odd, $ab$ is odd and $b^2$ is odd. This would imply that $a^2-ab+b^2 = 2^y =1$ which in turn implies that $a^3+b^3 = a+b \implies a=b.$ The problem I have is that if I would have considered that both $a$ and $b$ are even I would have gotten that $a=2t, b=2k$ from where $$8t^3+8k^3=2^c \implies t^3+k^3=2^{c-3}$$ but I couldn't deduce anything from here why cannot $a$ and $b$ be even?

答:
If $a$ and $b$ are both even, say $a=2^mA$ and $b=2^nB$ with $A$ and $B$ odd, then without loss of generality $n\geq m$ and so
$$2^c=a^3+b^3=2^{3m}\big(A^3+2^{3(n-m)}B^3\big),$$
from which it follows that
$$2^{c-3m}=A^3+2^{3(n-m)}B^3.$$
Because $A$ and $B$ are positive we see that $2^{c-3m}>1$, and so the left hand side is even. Because $A$ is odd it follows that also $2^{3(n-m)}B^3$ is odd, and so $n=m$. Then for $C=c-3m$ we have
$$A^3+B^3=2^C,$$
thus yielding a new solution with $A$ and $B$ both odd.

If $a$ and $b$ are both odd then you already observed that the factorization
$$2^c=a^3+b^3=(a+b)(a^2-ab+b^2),$$
implies that $a^2-ab+b^2=1$. Viewing this as a quadratic in $a$ shows that
$$a=\frac12\big(b\pm\sqrt{b^2-4(b^2-1)}\big)=\frac12\big(b\pm\sqrt{4-3b^2}\big).$$
For this to be an integer we must have $4-3b^2>0$, so $b=1$ as $b$ is positive by assumption. Then also $a=1$ as $a$ is positive by assumption. This shows that $a=b=1$. It follows that every solution is of the form $a=b=2^m$ for some nonegative integer $m$.


问:
fastest method to determine if two numbers are coprime
I am working on a mathematical problem that involves coprime integers. I wrote a computer program that allows me to search for the numbers I am looking for. However I am looking at a large set of integers and I have to compare many pairs of numbers and determine if they are coprime. My program has to do this so many times that any reduction in the calculation time for each pair of numbers would significantly reduce the overall run time of the program.

I am currently using the Euclidean algorithm.

http://en.wikipedia.org/wiki/Euclidean_algorithm

Even though the Euclidean algorithm is a very efficient method, I don't know if it's the fastest. I don't need the gcd of the two numbers I just need to determine if they are coprime or not.

My pseudocode:

while (B ≠ 0)

{T = B

B = A mod T

A = T}

where A and B are the pair of integers in question and T is a dummy variable used to hold a value to be used in a later calculation.
For those who haven't written a computer program before, while means that the process in the brackets will repeat until the condition in the parentheses is false.
At the end of the loop the variable A becomes the gcd of the original two integers.
if A=1 the two numbers are coprime if A>1 then the numbers are not coprime.

Even though the program above is simple, it is an iterative process and I'm looking for a method that only needs one or two steps.

Thanks in advance!

答:
Since you care about the speed of IsCoprime(n, m), I'm assuming that you're calling that function many times. So let's assume that we're minimizing the time the following code takes to run (K is some constant):

```<code>for (int n = 1; n <= K; ++n)
  for (int m = 1; m <= K; ++m)
    IsCoprime(n, m);
</code>```

You can precompute prime factors all ints up to K, which takes $O(K \log K)$, much smaller than the number of invocations of IsCoprime above, which is $O(K^2)$.

Then for each int up to K, compute its 32-bit "prime factor signature" sig[n].

Bit 0 is set if n is divisible by 2

Bit 1 is set if n is divisible by 3

Bit 2 is set if n is divisible by 5

...

Bit 30 is set if n is divisible by 113

Bit 31 is set if n is divisible by some prime > 113

Now, the first step you do in IsCoprime(n, m) is to compute binary and of the signatures of its arguments: X = sig[n] & sig[m]. If X is 0, then n and m are coprime. Otherwise, if some bit other than bit 31 of X is set, then n and m are not coprime. If neither of these conditions hold, you need to run some GCD algorithm to get the answer. However, you'll need to call GCD in a small number of cases.

One improvement you can make is having each of bits 16..31 represent multiple prime factors. For example, bit 16 would be set if n is divisible by any of the primes between 47 and 97, or something like that.

And of course you can always use more bits, like 64.

When I tried these techniques for K roughly 30,000, I got an over 10x speed improvement over (binary) GCD.

EDIT (2022-07-11)

Here's a concrete implementation of this idea:
https://gist.github.com/zielaj/cfdeca92fc0b8371164e4ca521d83587

For K = 0x4000 (16K), it runs in 0.337s on my laptop, vs 5.798s for binary GCD.

This code uses 64-bit signatures. The lower 32 bits are dedicated to the first 32 primes. Subsequent primes get 2 "random" upper bits each, an approach inspired by Bloom filters:
https://en.wikipedia.org/wiki/Bloom_filter

Here's the code snippet for the actual coprimality testing:

```<code>  inline bool AreCoprime(uxint n, uxint m) {
    if (n == 0 || m == 0) return n + m == 1;
    uxint sig = signatures[n] & signatures[m];

    // If the signatures are disjoint, then there are no prime factors
    // in common, so the numbers are coprime.
    if (sig == 0) return true;

    // If the signatures overlap somewhere in the first 32 bits, then
    // there's a common prime factor because each of these bits is
    // dedicated to a single prime.
    if ((sig & uniquebits) != 0) return false;

    // If there's at most one bit overlap (in the second half of the
    // signature), then there are no prime factors in common because
    // each of the primes in the second half gets 2 bits.
    if ((sig & (sig - 1)) == 0) return true;

    // If we're still undecided, fall back to the GCD computation.
    return bgcd(n, m) == 1;
  }
</code>```

Note that if you just want to generate pairs of small coprime integers, you can also use Stern-Brocot tree, which is O(1) per pair. However, when I tried that, using an admittedly unoptimized straightforward recursive implementation, it was still slower than the code above.
https://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree

Body:
Since you care about the speed of IsCoprime(n, m), I'm assuming that you're calling that function many times. So let's assume that we're minimizing the time the following code takes to run (K is some constant):

for (int n = 1; n <= K; ++n)
  for (int m = 1; m <= K; ++m)
    IsCoprime(n, m);

You can precompute prime factors all ints up to K, which takes $O(K \log K)$, much smaller than the number of invocations of IsCoprime above, which is $O(K^2)$.

Then for each int up to K, compute its 32-bit "prime factor signature" sig[n].

Bit 0 is set if n is divisible by 2

Bit 1 is set if n is divisible by 3

Bit 2 is set if n is divisible by 5

...

Bit 30 is set if n is divisible by 113

Bit 31 is set if n is divisible by some prime > 113

Now, the first step you do in IsCoprime(n, m) is to compute binary and of the signatures of its arguments: X = sig[n] & sig[m]. If X is 0, then n and m are coprime. Otherwise, if some bit other than bit 31 of X is set, then n and m are not coprime. If neither of these conditions hold, you need to run some GCD algorithm to get the answer. However, you'll need to call GCD in a small number of cases.

One improvement you can make is having each of bits 16..31 represent multiple prime factors. For example, bit 16 would be set if n is divisible by any of the primes between 47 and 97, or something like that.

And of course you can always use more bits, like 64.

When I tried these techniques for K roughly 30,000, I got an over 10x speed improvement over (binary) GCD.

EDIT (2022-07-11)

Here's a concrete implementation of this idea:
https://gist.github.com/zielaj/cfdeca92fc0b8371164e4ca521d83587

For K = 0x4000 (16K), it runs in 0.337s on my laptop, vs 5.798s for binary GCD.

This code uses 64-bit signatures. The lower 32 bits are dedicated to the first 32 primes. Subsequent primes get 2 "random" upper bits each, an approach inspired by Bloom filters:
https://en.wikipedia.org/wiki/Bloom_filter

Here's the code snippet for the actual coprimality testing:

  inline bool AreCoprime(uxint n, uxint m) {
    if (n == 0 || m == 0) return n + m == 1;
    uxint sig = signatures[n] & signatures[m];

    // If the signatures are disjoint, then there are no prime factors
    // in common, so the numbers are coprime.
    if (sig == 0) return true;

    // If the signatures overlap somewhere in the first 32 bits, then
    // there's a common prime factor because each of these bits is
    // dedicated to a single prime.
    if ((sig & uniquebits) != 0) return false;

    // If there's at most one bit overlap (in the second half of the
    // signature), then there are no prime factors in common because
    // each of the primes in the second half gets 2 bits.
    if ((sig & (sig - 1)) == 0) return true;

    // If we're still undecided, fall back to the GCD computation.
    return bgcd(n, m) == 1;
  }

Note that if you just want to generate pairs of small coprime integers, you can also use Stern-Brocot tree, which is O(1) per pair. However, when I tried that, using an admittedly unoptimized straightforward recursive implementation, it was still slower than the code above.
https://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree


问:
Every Cauchy sequence is bounded. Question about a detail in the proof.
To prove that every Cauchy sequence is bounded, we say that after some $k$ all $x_n$ are contained in a ball of given radius $\epsilon$ for $n \geq k$. We then say all $x_n$ with $1 \leq n \leq k-1$ are contained in a ball with radius given as the maximum distance between any two $x_n$ with $1 \leq n \leq k-1$. We make an argument that includes assuming this distance will be finite.

How do we know the distance will be finite? Can I not have a Cauchy sequence that comes in from infinity?

答:
Suppose we are in $\mathbb{R}$. It will be a natural extension to other metric spaces.

Proof: Let $\{a_j\}$ be a Cauchy sequence. We need to show $\exists M>0, M\in \mathbb{R}, s.t. |a_j|\leq M$, where $j=1,2,3,,,$. (Recall this is exactly the definition of boundedness.)

Well, at this moment, you might be tempted to let $M=max\{|a_1|,|a_2|,|a_3|,...,\}$. This is wrong, because we are not sure whether this maximum exists or not. It contains infinite terms. This is the difference between infinity and finiteness. For example, if $a_j=j,j=1,2,3,,,$, then you can easily see there is no maximum. But if this sequence only contains finite terms, then it is bounded.

Thus, we need to improve this approach. But anyway, the above idea is broadly correct. The correct proof is below:

Because $\{a_j\}$ is Cauchy, thus according to definition, $\forall \epsilon >0, \exists N\in \mathbb{N}$ such that whenever $j,k>N$, we have $|a_j-a_k|<\epsilon$.

Now for $\epsilon =1>0,\exists N\in \mathbb{N} $, call it $N_1,$ s.t. whenever $j,k>N_1$, we have $|a_j-a_k|<1$. Specifically, let $k=N_1+1>N_1,j>N_1$, then we have $|a_j-a_{N_1+1}|<1$.

This implies $|a_j|\leq|a_j-a_{N_1+1}|+|a_{N_1+1}|<1+|a_{N_1+1}|$. Notice that this line holds only when $j>N_1$.

Now $max\{|a_1|,|a_2|,|a_3|,...,|a_{N_1}|,1+|a_{N_1+1}|\}=M\in \mathbb{R}, M>0$ and $|a_j|\leq M$ for all $j$.

This $M$ is exactly what we need for the proof. Because when $j=1,2,3,...,N_1$,$|a_j|\leq M$. When $j>N_1$, then $|a_j|\leq 1+|a_{N_1+1}|\leq M$.


问:
$\lim_{n\to\infty} \frac{a^{2n}+1}{a^n+2}.$
I would like to ask why is the sequence convergent to $\dfrac{1}{2}$ when the parameter $|a|<1$ ?
At the same time, I would like to ask if there is a limit for $a<-1$, because the sequence would alternate with signs.

$$\lim_{n\to\infty} \frac{a^{2n}+1}{a^n+2}$$

答:
If $\lvert a\rvert<1,\ $ then $\displaystyle\lim_{n\to\infty} (a^{2n}+1) = 1,\ $ and $\displaystyle\lim_{n\to\infty} (a^{n}+2) = 2,\ $ so by the product rule for limits,

$\displaystyle\lim_{n\to\infty} \frac{a^{2n}+1}{a^n+2} = \frac{1}{2}.$

If $ a=1,\ $ then $\ \displaystyle\lim_{n\to\infty} \frac{a^{2n}+1}{a^n+2} = \frac{2}{3}.$

If $\ a = -1,\ $ or if $\ \lvert a\rvert>1,\ $ then the limit does not converge: if $\ a=-1,\ $ the sequence alternates between $2$ and $\frac{2}{3},\ $ if $\ a > 1,\ $it diverges to $\ +\infty,\ $ and finally if $\ a<-1,\ $ the sequence diverges by alternating between increasingly large negative and large positive numbers.


问:
Linear Algebra Done Right: Notation 1.23
I recently started reading Linear Algebra Done Right by Axler, and I find it great up until Notation 1.23, where the first bullet point states:

If $S$ is a set then $F^S$ denotes the set of functions from $S$ to $F$

I would really like to know what this means; in other words, does this mean that for all $f \in S$, then $f \in F$, but the only difference is that $F$ is a vector field?

答:
The question has already been answered, but here is a little context: the notation $Y^X$ is a little odd to denote the set of functions $X \rightarrow Y$. The origin of this notation lies in combinatorics, and more generally set theory.

Let $[n]$ be the set $\{1,\dots, n\}$. It is a classic motivational exercise in combinatorics to count the size of the set $\{f | f: [n] \rightarrow [m]\}$, and it turns out the answer is $m^n$ many functions (can you prove this?). So when $X$ and $Y$ are finite, we have the wonderful correspondence:

$$\left| Y^X\right| = |Y|^{|X|}$$

Moreover, once you have some cardinal arithmetic under your belt, we may extend this correspondence to infinite sets as well.


问:
Decomposing a rectangle in $\mathbb{R}^d$
Let $K=[a_1,b_1]\times\dots \times [a_d,b_d]$ be a closed rectangle in $\mathbb{R}^d$ and suppose that $K\subset\cup_{i=1}^n R_i$, where each $R_i$ is an open rectangle. In his measure theory book Cohn writes:

$K$ can be decomposed into a finite collection $\{K_j\}$ of rectangles that
overlap only on their boundaries and are such that for each $j$ the interior of $K_j$ is
included in some $R_i$.

If $\overline{R}_i$ denote the closure of $R_i$, then $K\cap\overline{R}_i$ is a closed rectangle. For each $1\leq m \leq d$, let $P_m$ denotes all the left and right $m$th coordinates appearing among the $K\cap\overline{R}_i$ $ (1\leq i\leq n)$. Then $P_m\subset [a_m,b_m]$, and if we order the elements of $P_m$ from left to right we obtain a partition of $[a_m,b_m]$ into a finite collection if closed intervals that overlap only at the boundary. Let $\{K_j\}$ denote the finite collection of all closed rectangles in $\mathbb{R}^d$ which are formed by taking $d$-products of those closed intervals (by choosing one closed interval in the partition of $[a_m,b_m]$ for each $m$). These rectangles intersect only at their boundaries and

$$K=\cup K_j$$

Indeed if $x\in K$, then $x_m \in [a_m,b_m]$ for each $m$, and so $x\in K_j$ for some $j$. Conversely if $x\in K_j$ for some $j$, then $x_m \in [a_m,b_m]$ for each $m$ and so $x\in K$.

Am stuck at proving that the interior of each $K_j$ is included in some $R_i$. It would suffice to show that $K_j\subset K\cap\overline{R}_i$ for some $i$. But I don't see how to show it.

Any help is greatly appreciated.

答: I can offer a ¨bootstrap¨ approach, which should really be a comment, but is too long. I think if you do the proof in $\mathbb R^2$ by first drawing a picture, the idea will be much clearer and extends easily to $\mathbb R^n.$ We have $K=[a,b]\times [c,d]$ and $R_i=[a_i,b_i]\times [c_i,d_i].$ In the first place, because $K$ is compact and $(\cup_{i=1}^n R_i)^c$ is closed, and disjoint from $K,\ d(K,(\cup_{i=1}^n R_i)^c)=r>0,$ so you may assume that $\cup_{i=1}^n R_i$ is itself an open rectangle $R$ containing $K$ and concentric with $K$. Then, the picture tells the story. We will take $\overline R_i\cap \overline R_j$ for $1\le i,j\le n$ to produce the required rectangles. Explicitly: the $R_i$ are a collection of rectangles, at least two of which must overlap,  whose union is $R$. Now, project each rectangle $\overline R_i\cap K$ on the $x$ axis and then on the $y$ axis. We get a partition $P_x$ of $[a,b]$ and $P_y$ of $[c,d]$. Using these partitions, we get a collection of almost disjoint rectangles whose union is $K$,  with the desired property that the interior of each $[x_k,x_{k+1}]\times [y_l,y_{l+1}]$ lies strictly in some $R_i$: indeed, suppose $(z_1,w_1)$ and $(z_2,w_2)$ are both interior to $[x_k,x_{k+1}]\times [y_l,y_{l+1}]$ but lie in different $R_i.$ Without loss of generality $z_1<z_2.$ Then, by construction there is an  $x\in P_x$ and such that $z_1<x<z_2.$ This is a contradiction because by construction, there are no partition points between $x_k$ and $x_{k+1}.$


问:
Question about basic predator prey modeling exercise

The Question

Consider a predator-prey population consisting of foxes and rabbits.
Without rabbits to eat, only $70$% of the foxes would survive each
month, while the fox population grows by $50$% of the rabbit
population each month due to the available food supply they represent.
In the absence of any foxes, the rabbit population would increase by
$20$% each month. The transition matrix $\mathbf{A}$ for this
situation is given. The constant $r > 0$ is the capture rate
representing the average number of rabbits consumed monthly by foxes.
If $r = 0.12$, show that in the long term the populations of foxes and
rabbits are stable, with $5$ foxes for each $3$ rabbits.

$$ \mathbf{A} = \begin{bmatrix} 0.7 & 0.5 \\ -r & 1.2 \end{bmatrix}. $$

My Understanding

In the following problem, they say $20$% increase in rabbit population formulates to $1.2R_k$, however, $70$% increase in the fox population formulates to $0.7F_k$. Shouldn't the $20$% increase in rabbit population formulate to $0.2R_k$?

答:
I believe that 'only 70% of the foxes would survive' indicates not a 70% increase of the fox population, but rather a 30% decrease! This will explain why it is $0.7F_{k}$ and not $1.7F_{k}$.

The rabbit population increase is in fact an increase as it is written and so should stay as $1.2R_{k}$.


问:
Exact probability distribution of waiting time on bus stop
I'm currently learn the Statistics 110: Probability by Joe Blitzstein at Harvard. There is a SP and HW 6. My question is based on 1-d of HW6.

Image of Problem Setting

Fred arrive at a uniform instant between the previous bus arrival and the next bus arrival. The average length of that interval between buses is 10 minutes. Since Fred arrive at any time in that interval, the average waiting time can be though as 5 minutes.

I understand this wrong intuition based on length-biasing. But what exact average waiting time and distribution of waiting time?

I try to use bus arriving time as prior. But stuck with starting point... Is there a good strategy to get this answer?

Image of My Approach

答:
When in doubt, refer to a specific example. Here is one which may clarify some confusion you're having.

Q: You arrive at the bus stop at 1:15pm and there is no bus in sight. If the last bus to pick up passengers departed at 1:00pm, what is the probability that you wait no more than $t$ minutes for the next bus to arrive?

A: Let $T$ be the random variable representing the amount of time you wait the next bus to arrive, and let $X$ the random variable denoting the amount of time between the departure of the 1:00pm bus and the arrival of the very next bus. Then $$P(T\leq t)=P(X\leq t+15|X>15)=\frac{P(15<X\leq t+15)}{P(X>15)}$$ Since $X\sim \text{Expo}\Big(\frac{1}{10}\Big)$ we have $$P(T \leq t)=\frac{\int_{15}^{t+15}\frac{1}{10}e^{-x/10}dx}{\int_{15}^{\infty}\frac{1}{10}e^{-x/10}dx}=1-e^{-t/10}$$ This shows that $T\sim \text{Expo}\Big(\frac{1}{10}\Big)$ as well. Would it matter if the previous bus departed at 12:00pm instead of 1:00pm? What if the bus you're waiting for is the first bus to arrive at the station? The answer is resounding no. The amount of time you wait for the next bus to arrive will always be exponentially distributed with mean $10$ minutes regardless of how much time elapsed since the arrival (or non$-$arrival) of the previous bus. This is what meant when we say that the exponential distribution is memoryless.

Hope this helps.


问:
Integral $\int_{-\infty}^\infty J^3_0(x) e^{i\omega x}\mathrm dx $
Hi I am trying to evaluate the integral
$$
\mathcal{I}(\omega)=\int_{-\infty}^\infty J^3_0(x) e^{i\omega x}\mathrm dx
$$
analytically.  We can also write
$$
\mathcal{I}(\omega)=\mathcal{FT}\big(J^3_0(x)\big)
$$ which is the Fourier Transform of the cube of Bessel function.  The Bessel function $J_0$ is given by
$$
J_0(x)=\frac{1}{2\pi}\int_{-\pi}^\pi e^{-ix\sin t} \mathrm dt.
$$
If it helps, we can represent the cube of the Bessel function by
$$
J^3_0(x)=-3\int J^2_0(x) J_1(x) \mathrm dx, \ \ \ \ \ J_1(x)=\frac{1}{2\pi}\int_{-\pi}^\pi e^{i(t-x\sin t)} \mathrm dt.
$$
In general
$$
J_n(x)=\frac{1}{2\pi}\int_{-\pi}^\pi e^{i(nt-x\sin t)}\mathrm  dt.
$$
The Fourier Transforms of the Bessel function and its square is given by
$$
\mathcal{FT}\big(J_0(x)\big)=\sqrt{\frac{2}{\pi}}\frac{\theta(\omega+1)-\theta(\omega-1)}{\sqrt{1-\omega^2}}
$$
and
$$
\mathcal{FT}\big(J^2_0(x)\big)=\frac{\sqrt{2}K\big(1-\frac{\omega^2}{4}\big)\big(\theta(-\omega-2)-1\big)\big(\theta(\omega-2)-1\big)}{\pi^{3/2}}
$$
where K is the elliptic-K function and $\theta$ is the heaviside step function.  However I need the cube...</p>

答:
Actually more is true: the Fourier transform of $J_0(ax)J_0(x)^2$ for any $a\in \mathbb{R}$ can be expressed in elliptic integral $K(m) = \int_0^1 \frac{dt}{\sqrt{(1-t^2)(1-mt^2)}}$.

Here is the explicit form of the already nontrivial case $a=1$: let $$\tag{1}G(w) = \frac{2 \sqrt{4-3 t}}{\pi ^2 w(1-t)}K(m_+)K(m_-)$$
with $$2v = 5-w^2+\sqrt{(w^2-9)(w^2-1)} \qquad t=\frac{v}{v-1}$$
$$4m_{\pm} = 2\pm v\sqrt{4-v} -(2-v)\sqrt{1-v}$$
then for $s\in \mathbb{R}$, our Fourier transform is $$\color{royalblue}{\int_0^\infty  J_0(t)^3 \cos(ts) dt} = -\lim_{\varepsilon\to 0^+}\Im[G(s+i\varepsilon)] $$

One has to be careful about branch problem though, see the end. Special cases:
$$\begin{aligned}\int_0^\infty J_0(x)^3 \cos x dx &= \frac{(2-\sqrt{2}) (\sqrt{2}+1)}{16 \pi ^3}\Gamma \left(\frac{1}{8}\right)^2 \Gamma \left(\frac{3}{8}\right)^2 \\
\int_0^\infty J_0(x)^3 \cos(\sqrt{5}x)dx &= \frac{1}{4\pi^3} \Gamma \left(\frac{3}{20}\right) \Gamma \left(\frac{7}{20}\right) \Gamma \left(\frac{9}{20}\right) \Gamma \left(\frac{21}{20}\right) \end{aligned}$$

Forget our notation of $G$ above, let
$$G(w) = \frac{1}{\pi^3}\int_{[0,\pi]^3} \frac{dx_1dx_2dx_3}{w-\cos x_1-\cos x_2 - \cos x_3}$$
then $G(w)$ is analytic in $\mathbb{C}-[-3,3]$. Using $\int_0^\pi e^{t\cos x} dx = \pi I_0(t)$ we have
$$G(w) = \frac{1}{\pi^3}\int_{[0,\pi]^3} \int_0^\infty e^{-t(w-\cos x_1-\cos x_2 - \cos x_3)} dx_i dt = \int_0^\infty e^{-tw} I_0(t)^3 dt$$
here we assume $w > 3$ to ensure convergence. By deforming contour, we can switch the path  of integral to be $\int_0^{i\infty}$ (integral over big circular arc $\to 0$ when $w>3$), so $$G(w) = i\int_0^\infty e^{-itw} J_0(t)^3 dt = -i\int_0^\infty e^{itw} J_0(t)^3 dt$$
Now RHS is analytic on $\Im w > 0$, so analytic continuation gives
$$G(w) = -i\int_0^\infty e^{itw} J_0(t)^3 dt \qquad \Im w > 0$$
In particular, we see for $s\in \mathbb{R}$, $\lim_{\varepsilon\to 0^+}G(s+i\varepsilon)$ exists, denote it by $G_{\Re}(s) - iG_{\Im}(s)$. Then above equality gives
$$G_{\Re}(s) = \int_0^\infty \sin(ts)J_0(t)^3 dt \qquad G_{\Im}(s) = \color{royalblue}{\int_0^\infty \cos(ts)J_0(t)^3 dt}$$
thus it suffices to show the triple integral actually equals RHS of $(1)$. The integral of $G_{\Re}(s)$ is not our goal, but we see it can be expressed as elliptic integral too.

The $G(w)$ is called Watson triple integral of simple cubic lattice. It turns out that the more general
$$G(w,a) = \frac{1}{\pi^3}\int_{[0,\pi]^3} \frac{dx_1dx_2dx_3}{w-a\cos x_1-\cos x_2 - \cos x_3}$$
called Watson triple integral of singly anisotropic cubic lattice can also be expressed in terms of $K$. Its closed-form evaluation is a culmination of ingenious symbolic computation, which will be only briefly recapitulated below, the reader are strongly encouraged to read the reference for this spectacular achievement.

[to be added later....]

$(1)$ holds at least for $w>3$ when principal branch of square root and $K$ is taken. Since $G(w)$ has no branch point on $\Im w > 0$ from the triple integral definition, $(1)$ is true for all $w \in \mathbb{C}-[-3,3]$ after analytic continuation.

For our concerned range $0<\Re w < 3, \Im w >0$, I think the only term that can cause deviation from principal branch is the term $\sqrt{(w^2-9)(w^2-1)}$ in $v$. After this has been considered, the following Mathematica code can calculate $G(w)$ in our range ($\Im w = 0$ not included)

```<code>G[w_] := Module[{x, y, v, t, m1, m2}, x = Re[w]; y = Im[w];
   If[5 x - x^3 + x*y^2 <= 0,
    v = 1/2 (5 - w^2 + Sqrt[(w^2 - 9) (w^2 - 1)]),
    v = 1/2 (5 - w^2 - Sqrt[(w^2 - 9) (w^2 - 1)])]; t = v/(v - 1);
   m1 = 1/2 (1 + v*Sqrt[4 - v]/2 - (2 - v) Sqrt[1 - v]/2);
   m2 = 1/2 (1 - v*Sqrt[4 - v]/2 - (2 - v) Sqrt[1 - v]/2);
   2/Pi^2/w*Sqrt[4 - 3 t]/(1 - t)*EllipticK[m1] EllipticK[m2]];
</code>```

Body:
Actually more is true: the Fourier transform of $J_0(ax)J_0(x)^2$ for any $a\in \mathbb{R}$ can be expressed in elliptic integral $K(m) = \int_0^1 \frac{dt}{\sqrt{(1-t^2)(1-mt^2)}}$.

Here is the explicit form of the already nontrivial case $a=1$: let $$\tag{1}G(w) = \frac{2 \sqrt{4-3 t}}{\pi ^2 w(1-t)}K(m_+)K(m_-)$$
with $$2v = 5-w^2+\sqrt{(w^2-9)(w^2-1)} \qquad t=\frac{v}{v-1}$$
$$4m_{\pm} = 2\pm v\sqrt{4-v} -(2-v)\sqrt{1-v}$$
then for $s\in \mathbb{R}$, our Fourier transform is $$\color{royalblue}{\int_0^\infty  J_0(t)^3 \cos(ts) dt} = -\lim_{\varepsilon\to 0^+}\Im[G(s+i\varepsilon)] $$

One has to be careful about branch problem though, see the end. Special cases:
$$\begin{aligned}\int_0^\infty J_0(x)^3 \cos x dx &= \frac{(2-\sqrt{2}) (\sqrt{2}+1)}{16 \pi ^3}\Gamma \left(\frac{1}{8}\right)^2 \Gamma \left(\frac{3}{8}\right)^2 \\
\int_0^\infty J_0(x)^3 \cos(\sqrt{5}x)dx &= \frac{1}{4\pi^3} \Gamma \left(\frac{3}{20}\right) \Gamma \left(\frac{7}{20}\right) \Gamma \left(\frac{9}{20}\right) \Gamma \left(\frac{21}{20}\right) \end{aligned}$$

Forget our notation of $G$ above, let
$$G(w) = \frac{1}{\pi^3}\int_{[0,\pi]^3} \frac{dx_1dx_2dx_3}{w-\cos x_1-\cos x_2 - \cos x_3}$$
then $G(w)$ is analytic in $\mathbb{C}-[-3,3]$. Using $\int_0^\pi e^{t\cos x} dx = \pi I_0(t)$ we have
$$G(w) = \frac{1}{\pi^3}\int_{[0,\pi]^3} \int_0^\infty e^{-t(w-\cos x_1-\cos x_2 - \cos x_3)} dx_i dt = \int_0^\infty e^{-tw} I_0(t)^3 dt$$
here we assume $w > 3$ to ensure convergence. By deforming contour, we can switch the path  of integral to be $\int_0^{i\infty}$ (integral over big circular arc $\to 0$ when $w>3$), so $$G(w) = i\int_0^\infty e^{-itw} J_0(t)^3 dt = -i\int_0^\infty e^{itw} J_0(t)^3 dt$$
Now RHS is analytic on $\Im w > 0$, so analytic continuation gives
$$G(w) = -i\int_0^\infty e^{itw} J_0(t)^3 dt \qquad \Im w > 0$$
In particular, we see for $s\in \mathbb{R}$, $\lim_{\varepsilon\to 0^+}G(s+i\varepsilon)$ exists, denote it by $G_{\Re}(s) - iG_{\Im}(s)$. Then above equality gives
$$G_{\Re}(s) = \int_0^\infty \sin(ts)J_0(t)^3 dt \qquad G_{\Im}(s) = \color{royalblue}{\int_0^\infty \cos(ts)J_0(t)^3 dt}$$
thus it suffices to show the triple integral actually equals RHS of $(1)$. The integral of $G_{\Re}(s)$ is not our goal, but we see it can be expressed as elliptic integral too.

The $G(w)$ is called Watson triple integral of simple cubic lattice. It turns out that the more general
$$G(w,a) = \frac{1}{\pi^3}\int_{[0,\pi]^3} \frac{dx_1dx_2dx_3}{w-a\cos x_1-\cos x_2 - \cos x_3}$$
called Watson triple integral of singly anisotropic cubic lattice can also be expressed in terms of $K$. Its closed-form evaluation is a culmination of ingenious symbolic computation, which will be only briefly recapitulated below, the reader are strongly encouraged to read the reference for this spectacular achievement.

[to be added later....]

$(1)$ holds at least for $w>3$ when principal branch of square root and $K$ is taken. Since $G(w)$ has no branch point on $\Im w > 0$ from the triple integral definition, $(1)$ is true for all $w \in \mathbb{C}-[-3,3]$ after analytic continuation.

For our concerned range $0<\Re w < 3, \Im w >0$, I think the only term that can cause deviation from principal branch is the term $\sqrt{(w^2-9)(w^2-1)}$ in $v$. After this has been considered, the following Mathematica code can calculate $G(w)$ in our range ($\Im w = 0$ not included)

G[w_] := Module[{x, y, v, t, m1, m2}, x = Re[w]; y = Im[w];
   If[5 x - x^3 + x*y^2 <= 0,
    v = 1/2 (5 - w^2 + Sqrt[(w^2 - 9) (w^2 - 1)]),
    v = 1/2 (5 - w^2 - Sqrt[(w^2 - 9) (w^2 - 1)])]; t = v/(v - 1);
   m1 = 1/2 (1 + v*Sqrt[4 - v]/2 - (2 - v) Sqrt[1 - v]/2);
   m2 = 1/2 (1 - v*Sqrt[4 - v]/2 - (2 - v) Sqrt[1 - v]/2);
   2/Pi^2/w*Sqrt[4 - 3 t]/(1 - t)*EllipticK[m1] EllipticK[m2]];


问:
If $a-b$ divides the difference $f(a)-f(b)$, must $f$ be an integer polynomial?
Background: Suppose $f:\mathbb{Z}\rightarrow\mathbb{Z}$ is an integer polynomial. Then $a-b|f(a)-f(b)$ for distinct integers $a, b$. This can be proven by induction on the number of terms in $f$ as well as the degree for monomials.

However, what if we consider the converse? If $f:\mathbb{Z}\rightarrow\mathbb{Z}$ is a function satisfying $a-b|f(a)-f(b)$, must it be an integer polynomial? Must it even be a polynomial?

答:
The converse is false. Consider the function $f(x)=\frac{x^4+x^2}{2}$.

\begin{align}
f(a)-f(b)&=\frac{a^4-b^4+a^2-b^2}{2}\\
&=(a-b)\times\frac{(a+b)(a^2+b^2+1)}{2}
\end{align}

Note that $\frac{(a+b)(a^2+b^2+1)}{2}$ is always an integer, if $a+b$ is even we are done, otherwise, $a,b$ will have different parity, and $a^2,b^2$ will have different parity, hence $a^2+b^2+1$ would be even.

It is also well-known that if $f:\mathbb{Z}\rightarrow\mathbb{Z}$ is a polynomial function, then $f$ must be a sum of binomial coefficients. Specifically, there are integers $\{a_k\}_{k=0}^n$ such that $f(x)=\sum_{k=0}^na_k\binom{x}{k}$.

Note that since every finite list of points $(x_i,y_i)$ can interpolated with a polynomial, the only way we are going to get a non-polynomial is if we consider a function defined on an infinite set of points. Here, we can consider $f(x)=\sum_{0\leq k<|x|}\prod_{-k\leq i\leq k}(x-i)$.

For every restriction $f|_{[-n,n]}$ we see $f|_{[-n,n]}(x)=\sum_{0\leq k<n}\prod_{-k\leq i\leq k}(x-i)$, which is a polynomial. Hence, $a-b|f(a)-f(b)$. However, there is no polynomial $p(x)$ such that $p(x)=f(x)$ for all $x$, since if $\deg(p)=k$, then $f|_{[-2k,2k]}$ is a polynomial of degree $4k-1$, which cannot equal $p(x)$ on $[-k,k]$.


问:
Square root of $8^3$
I'm only in intermediate algebra. I know that $\sqrt{8^3}$ is equal to $16\sqrt{2}$ but could you simply explain the process on how to get to that? </p>

Title: Square root of $8^3$

Body: $\sqrt[]{8^3}$ $= \sqrt[]{8^2\cdot8}$ $= 8\sqrt[]{8}$ $=8\sqrt[]{2\cdot4}$ $=2\cdot8\sqrt[]{2}$ $=16\sqrt[]{2}$


问:
Projection into upper-half of a plane
I have the following problem: given a vector $v\in\mathbb{R}^n$ (if it matters, its values are only from $\pm1$) I need to find a vector that maximizes some function, and follows the two constraints:

the vector is positive (for every i, proj(u)i≥0)

the vector is orthogonal to v.

Im using a version of the gradient descent algorithm with a "projection" step to find the solution, and the "projection" step takes any vector and converts it into a "valid" vector.

I want to find an algorithm for this "projection" step, but I dont understand how to satisfy both constaints together and not only one of them.

I would be glad to get some help!

答:
I think the 'algorithm' shall consist of the following 2 steps:

Step 1: Project $u$ onto $v^{\perp}$. From the problem statement I believe you already know the most efficient way to do this.

For step 2 you must realize that the intersection of $v^{\perp}$ with the non-negative orthant (this is what you call the vector being non-negative) is a (possibly trivial as I showed in the comment) convex cone.

Therefore step 2 is to project the projected vector $u'$ onto this convex cone. I have a reference which goes into detail on how to do this even in the case of a Hilbert space. This will hopefully be strong enough to handle your case as well. Actually when proceeding algorithmically for large n you will likely employ these approximation methods.

Projections onto convex cones in Hilbert space, John M. Ingram, M.M. Marsh ,Journal of Approximation Theory, Volume 64, Issue 3, March 1991, Pages 343-350

https://www.sciencedirect.com/science/article/pii/002190459190067K

Hopefully it was helpful. Sorry for outsourcing the crux of the problem to a reference. It is just that the statement is a bit too generic to fully resolve it in a small post here.

Title: Projection into upper-half of a plane


问:
Is there a relation that is neither reflexive nor transitive nor symmetric or anti-symmetric
Can anyone help me with this question i got from discrete, perhaps my understanding is not good enough and I've been stuck trying to think of a possible relation that could work.

It asked for a relation on R {a,b,c}

答:
hardmath’s comment is right on the money: you need to look at the definitions of reflexivity, antisymmetry, transitivity, and symmetry and see exactly what it takes to ensure that $R$ does not have each of these properties. Take them one at a time. It helps to have a diagram of $\{a,b,c\}\times\{a,b,c\}$ in front of you, since $R$ is a subset of that set: you can use it to help you keep track of which of the $9$ possible ordered pairs you want to keep in $R$, and which ones you want to keep out of $R$. I’ll give you a good start on the task and leave the rest to you to finish.

$$\begin{array}{ccc}
\langle a,c\rangle&\langle b,c\rangle&\langle c,c\rangle\\
\langle a,b\rangle&\langle b,b\rangle&\langle c,b\rangle\\
\langle a,a\rangle&\langle b,a\rangle&\langle c,a\rangle
\end{array}$$

If $R$ is not reflexive, there must be some $x\in\{a,b,c\}$ such that $x\not\mathrel{R}x$. You can pick any of the members of $\{a,b,c\}$ to fill this rôle; let’s pick $a$ and color $\langle a,a\rangle$ blue to indicate that it definitely is not in $R$:

$$\begin{array}{ccc}
\langle a,c\rangle&\langle b,c\rangle&\langle c,c\rangle\\
\langle a,b\rangle&\langle b,b\rangle&\langle c,b\rangle\\
\color{blue}{\langle a,a\rangle}&\langle b,a\rangle&\langle c,a\rangle
\end{array}$$

If $R$ is not antisymmetric, there must be some $x,y\in\{a,b,c\}$ such that $x\mathrel{R}y$, and $y\mathrel{R}x$, but $x\ne y$. Let’s try using $a$ and $b$; if that doesn’t work out, we can always back up and try a different pair. Using red to indicate ordered pairs that definitely are in $R$, we now have:

$$\begin{array}{ccc}
\langle a,c\rangle&\langle b,c\rangle&\langle c,c\rangle\\
\color{red}{\langle a,b\rangle}&\langle b,b\rangle&\langle c,b\rangle\\
\color{blue}{\langle a,a\rangle}&\color{red}{\langle b,a\rangle}&\langle c,a\rangle
\end{array}$$

If $R$ is not transitive, there must be some $x,y,x\in\{a,b,c\}$ such that $x\mathrel{R}y$, and $y\mathrel{R}z$, but $x\not\mathrel{R}z$. Note that $x,y$, and $z$ are not all required to be distinct. We already have such an example just in the ordered pairs whose status vis à vis $R$ has been decided; I leave it to you to find it.

If $R$ is not symmetric, there must be some $x,y\in\{a,b,c\}$ such that $x\mathrel{R}y$, but $y\not\mathrel{R}x$. I’ll leave this one to you; there are several ways to complete the construction of $R$ so that it is not symmetric.


问:
Is there a closed form for the distribution of $T = \sum_{k=0}^\infty 2^{-k} X_k$?
Let
$$T = \sum_{k=0}^\infty 2^{-k} X_k$$

Where each $X_k \sim \text{Exp}(1)$ is i.i.d. as an exponential random variable with $\lambda = 1$. Is there a closed form for the pdf or cdf of $T$?

答:
A few notes that might be helpful.

Suppose $0 < a_0 < a_1 < \cdots$ and that
$X$ has density
\begin{equation*}
 f(x) = \sum_{m=0}^{M-1} C_m e^{-a_m x}
\end{equation*}
on $x \geq 0$, where the $C_m$ are not necessarily nonnegative, and that $Y$ is
independent and distributed as $a_M e^{-a_M y}$, $y \geq 0$.
Then $Z = X + Y$ has density
\begin{align*}
 f_Z(z) &= \int_0^z f(x) a_M e^{-a_M(z - x)}\, dx \\
 &= \int_0^z\, \sum_{m=0}^{M-1}a_M C_m e^{-a_mx}e^{-a_Mz + a_Mx}\, dx \\
 &= \sum_{m=0}^{M-1}a_M C_m e^{-a_Mz}\int_0^z\, e^{-a_mx}e^{a_Mx}\, dx \\
 &= \sum_{m=0}^{M-1}a_M C_m e^{-a_Mz}\int_0^z\, e^{(a_M - a_m)x}\, dx \\
 &= \sum_{m=0}^{M-1}\frac{a_M C_m}{a_M - a_m} e^{-a_Mz} (e^{(a_M - a_m)z} - 1) \\
 &= \sum_{m=0}^{M-1}\frac{a_M C_m}{a_M - a_m} (e^{-a_mz} - e^{-a_Mz}) \\
 &= \sum_{m=0}^{M-1}\frac{a_M C_m}{a_M - a_m} e^{-a_mz}
 - \bigl( \sum_{m=0}^{M-1}\frac{a_M C_m}{a_M - a_m}\bigr) e^{-a_Mz}
\end{align*}
which shows $f_Z$ has a form similar to the above:
\begin{equation*}
 f_Z(z) = \sum_{m=0}^M C'_m e^{-a_m z}
\end{equation*}
with
\begin{equation*}
 C'_m = \frac{a_M C_m}{a_M - a_m}
\end{equation*}
for $m = 0, \dots, M-1$ and
\begin{equation*}
 C'_M = -\sum_{m=0}^{M-1} \frac{a_M C_m}{a_M - a_m}.
\end{equation*}
This lends itself to an iteration constructing the limiting density as $M \rightarrow \infty$, at least when it exists.

The original question involves $a_m = 2^m$ so we expect a density of the form
\begin{equation*}
 f_\infty(z) = D_0e^{-z} + D_1e^{-2z} + D_2e^{-4z} + D_3e^{-8z} + \dots
\end{equation*}
The recursion for the leading coefficient yields
$D_0 = 1/ \prod_{k=1}^\infty (1 - 2^{-k}) \approx 3.462746619$.

ADDED

The first few coefficients, computed using the recurrence above, are

\begin{align*}
m &\qquad\qquad D_m \\
0 &\qquad +3.46274662e+00 \\
1 &\qquad -6.92549324e+00 \\
2 &\qquad +4.61699549e+00 \\
3 &\qquad -1.31914157e+00 \\
4 &\qquad +1.75885543e-01 \\
5 &\qquad -1.13474544e-02 \\
6 &\qquad +3.60236646e-04 \\
7 &\qquad -5.67301805e-06 \\
8 &\qquad +4.44942599e-08 \\
9 &\qquad -1.74147636e-10
\end{align*}


问:
Simplest algorithm to cover a sphere
What is the simplest algorithm for covering the surface of a sphere by walking. To word it another way, what would be the simplest algorithm a person could take to walk the surface of the earth?</p>

答:
Start at the South Pole, and walk north along the line of longitude that represents Greenwich Mean Time.  Travel along this line of longitude via the following algorithm:

Take 1 step north.

Then make a complete circle along the corresponding line of latitude until you return to the pertinent line of longitude.

Then, rinse and repeat until you reach the North Pole.

Title: Simplest algorithm to cover a sphere


问:
How many four digit numbers in which each digit is at least as large as the previous digit?
Given that the first digit has to be between 1 and 9, each subsequent digit depends on the previous. If they were strictly increasing, then it would be $\binom{9}{4}$ numbers. My idea is that for each digit after the first, there is an additional choice compared to the strictly increasing numbers, but I'm not sure how to translate that into an expression. Any help is appreciated!

答:
Hint:

If $$1\leq a_1<a_2<a_3<a_4\leq 12$$ then $$1\leq a_1\leq a_2-1\leq a_3-2\leq a_4-3\leq  9,$$
and visa versa.


答:
Think about this figure (for the 3-digit case):

$$\sum\limits_{a_1 = 1}^9 \sum\limits_{a_2 = a_1}^9 \sum\limits_{a_3 = a_2}^9 \sum\limits_{a_4 = a_3}^9 1 = 495$$

Title: How many four digit numbers in which each digit is at least as large as the previous digit?

Body: Given that the first digit has to be between 1 and 9, each subsequent digit depends on the previous. If they were strictly increasing, then it would be $\binom{9}{4}$ numbers. My idea is that for each digit after the first, there is an additional choice compared to the strictly increasing numbers, but I'm not sure how to translate that into an expression. Any help is appreciated!


问:
Generate a value given three other values with caps
Given a Target $T$ whose value is a positive integer. And, given a $3$ integer tuple $(N_1,N_2,N_3)$ where the value of $N_1$ is $N_1$ times $2$; the value of $N_2$ is $N_2$ times $3$; and the value of N3 is N3 times 4 is there a simple way to work out all possible values for N1, N2 and N3 so that T = (N1 *2)+(N2 * 3)+(N3 * 4).  Importantly N1, N2 and N3 have proscribed bounds that may be larger than the value of T. For example:

$T= 123$

$3$ int tuple = $(300, 3, 200) = 1409: (600+9+800)$

With this in mind, I'm seeking a way to generate all combinations of (N1, N2, N3) that will equal T. for example, where $T=123, (50, 1, 5) = 123 or (0, 1, 30) = 123$

EDIT: N1, N2, and N3 must be whole numbers with a value of 0 or greater.

To add some further clarity, if solving this were being approached through code one method of solving would be as follows:

```<code>T = 123
my_tuple = (300,3,200)
good_combo = []

 for twos in range((my_tuple[1]), -1, -1):
            num_twos = twos*2
            for threes in range((my_tuple[2]), -1, -1):
                num_threes = threes * 3
                for fours in range((my_tuple[3]), -1, -1):
                    num_fours = fours * 4
                    combo = num_twos + num_threes + num_fours
                    if my_tuple == T:
                        good_combo.append((twos, threes, fours))
</code>```

The problem with the above approach is that it is far too slow when you are dealing with large numbers.

Apologies if this is a really simply question. I'm trying to improve my maths.

Thanks for reading

答:
Everyone is wondering how N1=2N1 while I am wondering what N1, N2, N3 have proscribed bounds that may be larger than T means.

Basically you want $T=2N_1+3N_2+4N_3=2(N_1+2N_3)+3N_2$ with N being integers right? Well it might be easier to deal with an example so let's pick T=123 as you did. $N_2=\frac{123-2(N_1+2N_3)}{3}=41-\frac 2 3(N_1+2N_3)$.

The only way N2 can be an integer is if N1+2N3 is divisible by 3. So let $N_1+2N_3=3c,c\in\mathbb Z$. If N1, N2, N3 can be negative integers, there are infinitely many solutions. If they have to be positive or there are other restrictions, there could be finitely many solutions. Let's say that they all have to positive. Then $N_2=41-2c, c=20,19,...,-40,-41$. And $N_1+2N_3=3c$. For c=20, we have N1+2N3=60, so pairs are (0,30),(2,29), (4,28),...,(58,1), (60,0). For c=19, we have N1+2N3=57, so pairs are (1,28),(3,27),...,(57,0), and finally for c=-123 we have N1+2N3=-41. So we assumed N is positive so let's actually back up to um c=1. Then N1+2N3=3. So pairs are (1,1), (3,0). And for c=0, the pair is (0,0). So we've solved for all possibilities. They're

$$\begin{matrix}c&N_2&(N_1,N_3)\\
20&1&(0,30),(2,29), (4,28),...,(58,1), (60,0)\\
19&3&(1,28),(3,27),...,(57,0)\\
...\\
1&39&(1,1), (3,0)\\
0&41&(0,0)\end{matrix}$$

Let's see if one of them works, N1=3,N2=3,N3=27. We get 6+9+108=123.

Now for an algorithm, you surely know how to make an algorithm for this. Let's say N1 can be between -20 and 40, N2 can be between -30 and 50, N3 can be between -3 and 30. Try all the possibilities and select the ones that work.

```<code>N1=-20:40
N2=-30:50
N3=-3:30
T=123
oks=matrix(0, ncol=3, nrow=1)
for (i in N1) {
  for (j in N2) {
    for (k in N3) {
      if (2*i+3*j+4*k==T) {
        oks=rbind(oks, matrix(c(i,j,k), ncol=3))
      }
    }
  }
}
oks=oks[-1,]
</code>```

Values that work

```<code>> head(oks)
     [,1] [,2] [,3]
[1,]  -20   17   28
[2,]  -20   21   25
[3,]  -20   25   22
[4,]  -20   29   19
[5,]  -20   33   16
[6,]  -20   37   13
> tail(oks)
       [,1] [,2] [,3]
[670,]   40   -3   13
[671,]   40    1   10
[672,]   40    5    7
[673,]   40    9    4
[674,]   40   13    1
[675,]   40   17   -2
> print(oks)
       [,1] [,2] [,3]
  [1,]  -20   17   28
  [2,]  -20   21   25
  [3,]  -20   25   22
  [4,]  -20   29   19
  [5,]  -20   33   16
  [6,]  -20   37   13
  [7,]  -20   41   10
  [8,]  -20   45    7
  [9,]  -20   49    4
 [10,]  -19   15   29
 [11,]  -19   19   26
 [12,]  -19   23   23
 [13,]  -19   27   20
 [14,]  -19   31   17
 [15,]  -19   35   14
 [16,]  -19   39   11
 [17,]  -19   43    8
 [18,]  -19   47    5
 [19,]  -18   13   30
 [20,]  -18   17   27
 [21,]  -18   21   24
 [22,]  -18   25   21
 [23,]  -18   29   18
 [24,]  -18   33   15
 [25,]  -18   37   12
 [26,]  -18   41    9
 [27,]  -18   45    6
 [28,]  -18   49    3
 [29,]  -17   15   28
 [30,]  -17   19   25
 [31,]  -17   23   22
 [32,]  -17   27   19
 [33,]  -17   31   16
 [34,]  -17   35   13
 [35,]  -17   39   10
 [36,]  -17   43    7
 [37,]  -17   47    4
 [38,]  -16   13   29
 [39,]  -16   17   26
 [40,]  -16   21   23
 [41,]  -16   25   20
 [42,]  -16   29   17
 [43,]  -16   33   14
 [44,]  -16   37   11
 [45,]  -16   41    8
 [46,]  -16   45    5
 [47,]  -16   49    2
 [48,]  -15   11   30
 [49,]  -15   15   27
 [50,]  -15   19   24
 [51,]  -15   23   21
 [52,]  -15   27   18
 [53,]  -15   31   15
 [54,]  -15   35   12
 [55,]  -15   39    9
 [56,]  -15   43    6
 [57,]  -15   47    3
 [58,]  -14   13   28
 [59,]  -14   17   25
 [60,]  -14   21   22
 [61,]  -14   25   19
 [62,]  -14   29   16
 [63,]  -14   33   13
 [64,]  -14   37   10
 [65,]  -14   41    7
 [66,]  -14   45    4
 [67,]  -14   49    1
 [68,]  -13   11   29
 [69,]  -13   15   26
 [70,]  -13   19   23
 [71,]  -13   23   20
 [72,]  -13   27   17
 [73,]  -13   31   14
 [74,]  -13   35   11
 [75,]  -13   39    8
 [76,]  -13   43    5
 [77,]  -13   47    2
 [78,]  -12    9   30
 [79,]  -12   13   27
 [80,]  -12   17   24
 [81,]  -12   21   21
 [82,]  -12   25   18
 [83,]  -12   29   15
 [84,]  -12   33   12
 [85,]  -12   37    9
 [86,]  -12   41    6
 [87,]  -12   45    3
 [88,]  -12   49    0
 [89,]  -11   11   28
 [90,]  -11   15   25
 [91,]  -11   19   22
 [92,]  -11   23   19
 [93,]  -11   27   16
 [94,]  -11   31   13
 [95,]  -11   35   10
 [96,]  -11   39    7
 [97,]  -11   43    4
 [98,]  -11   47    1
 [99,]  -10    9   29
[100,]  -10   13   26
[101,]  -10   17   23
[102,]  -10   21   20
[103,]  -10   25   17
[104,]  -10   29   14
[105,]  -10   33   11
[106,]  -10   37    8
[107,]  -10   41    5
[108,]  -10   45    2
[109,]  -10   49   -1
[110,]   -9    7   30
[111,]   -9   11   27
[112,]   -9   15   24
[113,]   -9   19   21
[114,]   -9   23   18
[115,]   -9   27   15
[116,]   -9   31   12
[117,]   -9   35    9
[118,]   -9   39    6
[119,]   -9   43    3
[120,]   -9   47    0
[121,]   -8    9   28
[122,]   -8   13   25
[123,]   -8   17   22
[124,]   -8   21   19
[125,]   -8   25   16
[126,]   -8   29   13
[127,]   -8   33   10
[128,]   -8   37    7
[129,]   -8   41    4
[130,]   -8   45    1
[131,]   -8   49   -2
[132,]   -7    7   29
[133,]   -7   11   26
[134,]   -7   15   23
[135,]   -7   19   20
[136,]   -7   23   17
[137,]   -7   27   14
[138,]   -7   31   11
[139,]   -7   35    8
[140,]   -7   39    5
[141,]   -7   43    2
[142,]   -7   47   -1
[143,]   -6    5   30
[144,]   -6    9   27
[145,]   -6   13   24
[146,]   -6   17   21
[147,]   -6   21   18
[148,]   -6   25   15
[149,]   -6   29   12
[150,]   -6   33    9
[151,]   -6   37    6
[152,]   -6   41    3
[153,]   -6   45    0
[154,]   -6   49   -3
[155,]   -5    7   28
[156,]   -5   11   25
[157,]   -5   15   22
[158,]   -5   19   19
[159,]   -5   23   16
[160,]   -5   27   13
[161,]   -5   31   10
[162,]   -5   35    7
[163,]   -5   39    4
[164,]   -5   43    1
[165,]   -5   47   -2
[166,]   -4    5   29
[167,]   -4    9   26
[168,]   -4   13   23
[169,]   -4   17   20
[170,]   -4   21   17
[171,]   -4   25   14
[172,]   -4   29   11
[173,]   -4   33    8
[174,]   -4   37    5
[175,]   -4   41    2
[176,]   -4   45   -1
[177,]   -3    3   30
[178,]   -3    7   27
[179,]   -3   11   24
[180,]   -3   15   21
[181,]   -3   19   18
[182,]   -3   23   15
[183,]   -3   27   12
[184,]   -3   31    9
[185,]   -3   35    6
[186,]   -3   39    3
[187,]   -3   43    0
[188,]   -3   47   -3
[189,]   -2    5   28
[190,]   -2    9   25
[191,]   -2   13   22
[192,]   -2   17   19
[193,]   -2   21   16
[194,]   -2   25   13
[195,]   -2   29   10
[196,]   -2   33    7
[197,]   -2   37    4
[198,]   -2   41    1
[199,]   -2   45   -2
[200,]   -1    3   29
[201,]   -1    7   26
[202,]   -1   11   23
[203,]   -1   15   20
[204,]   -1   19   17
[205,]   -1   23   14
[206,]   -1   27   11
[207,]   -1   31    8
[208,]   -1   35    5
[209,]   -1   39    2
[210,]   -1   43   -1
[211,]    0    1   30
[212,]    0    5   27
[213,]    0    9   24
[214,]    0   13   21
[215,]    0   17   18
[216,]    0   21   15
[217,]    0   25   12
[218,]    0   29    9
[219,]    0   33    6
[220,]    0   37    3
[221,]    0   41    0
[222,]    0   45   -3
[223,]    1    3   28
[224,]    1    7   25
[225,]    1   11   22
[226,]    1   15   19
[227,]    1   19   16
[228,]    1   23   13
[229,]    1   27   10
[230,]    1   31    7
[231,]    1   35    4
[232,]    1   39    1
[233,]    1   43   -2
[234,]    2    1   29
[235,]    2    5   26
[236,]    2    9   23
[237,]    2   13   20
[238,]    2   17   17
[239,]    2   21   14
[240,]    2   25   11
[241,]    2   29    8
[242,]    2   33    5
[243,]    2   37    2
[244,]    2   41   -1
[245,]    3   -1   30
[246,]    3    3   27
[247,]    3    7   24
[248,]    3   11   21
[249,]    3   15   18
[250,]    3   19   15
[251,]    3   23   12
[252,]    3   27    9
[253,]    3   31    6
[254,]    3   35    3
[255,]    3   39    0
[256,]    3   43   -3
[257,]    4    1   28
[258,]    4    5   25
[259,]    4    9   22
[260,]    4   13   19
[261,]    4   17   16
[262,]    4   21   13
[263,]    4   25   10
[264,]    4   29    7
[265,]    4   33    4
[266,]    4   37    1
[267,]    4   41   -2
[268,]    5   -1   29
[269,]    5    3   26
[270,]    5    7   23
[271,]    5   11   20
[272,]    5   15   17
[273,]    5   19   14
[274,]    5   23   11
[275,]    5   27    8
[276,]    5   31    5
[277,]    5   35    2
[278,]    5   39   -1
[279,]    6   -3   30
[280,]    6    1   27
[281,]    6    5   24
[282,]    6    9   21
[283,]    6   13   18
[284,]    6   17   15
[285,]    6   21   12
[286,]    6   25    9
[287,]    6   29    6
[288,]    6   33    3
[289,]    6   37    0
[290,]    6   41   -3
[291,]    7   -1   28
[292,]    7    3   25
[293,]    7    7   22
[294,]    7   11   19
[295,]    7   15   16
[296,]    7   19   13
[297,]    7   23   10
[298,]    7   27    7
[299,]    7   31    4
[300,]    7   35    1
[301,]    7   39   -2
[302,]    8   -3   29
[303,]    8    1   26
[304,]    8    5   23
[305,]    8    9   20
[306,]    8   13   17
[307,]    8   17   14
[308,]    8   21   11
[309,]    8   25    8
[310,]    8   29    5
[311,]    8   33    2
[312,]    8   37   -1
[313,]    9   -5   30
[314,]    9   -1   27
[315,]    9    3   24
[316,]    9    7   21
[317,]    9   11   18
[318,]    9   15   15
[319,]    9   19   12
[320,]    9   23    9
[321,]    9   27    6
[322,]    9   31    3
[323,]    9   35    0
[324,]    9   39   -3
[325,]   10   -3   28
[326,]   10    1   25
[327,]   10    5   22
[328,]   10    9   19
[329,]   10   13   16
[330,]   10   17   13
[331,]   10   21   10
[332,]   10   25    7
[333,]   10   29    4
 [ reached getOption("max.print") -- omitted 342 rows ]
</code>```

Try one of them

```<code>> -10*2 +  41*3   + 5*4
[1] 123
</code>```

Update

```<code>T=123
my=c(300, 2, 200)
ans=matrix(0, ncol=3)
for (N1 in seq(max(0, (T-3*my[2]-4*my[3])/2), min(T/2, my[1]))) {
  for (N2 in seq(max(0, (T-2*N1-4*my[3])/3), min(my[2], (T-2*N1)/3))) {
    N3=T-2*N1-3*N2
    if (N3 %% 4 == 0) {
      ans=rbind(ans, matrix(c(N1, N2, N3/4), nrow=1))
    }
  }
}
ans=ans[-1,]
ans

for (k in 1:nrow(ans)) {
  print(ans[k,1]*2+ans[k,2]*3+ans[k,3]*4==T)
}

n=0
for (k in 0:my[1]) {
  for (j in 0:my[2]) {
    for (i in 0:my[3]) {
      if (k*2+j*3+i*4==T) n=n+1
    }
  }
}
print(n)
</code>```

out

```<code>> ans
      [,1] [,2] [,3]
 [1,]    0    1   30
 [2,]    2    1   29
 [3,]    4    1   28
 [4,]    6    1   27
 [5,]    8    1   26
 [6,]   10    1   25
 [7,]   12    1   24
 [8,]   14    1   23
 [9,]   16    1   22
[10,]   18    1   21
[11,]   20    1   20
[12,]   22    1   19
[13,]   24    1   18
[14,]   26    1   17
[15,]   28    1   16
[16,]   30    1   15
[17,]   32    1   14
[18,]   34    1   13
[19,]   36    1   12
[20,]   38    1   11
[21,]   40    1   10
[22,]   42    1    9
[23,]   44    1    8
[24,]   46    1    7
[25,]   48    1    6
[26,]   50    1    5
[27,]   52    1    4
[28,]   54    1    3
[29,]   56    1    2
[30,]   58    1    1
[31,]   60    1    0

> for (k in 1:nrow(ans)) {
+   print(ans[k,1]*2+ans[k,2]*3+ans[k,3]*4==T)
+ }
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE

> print(n)
[1] 31
<span class="math-container">```
```

Body:
Everyone is wondering how N1=2N1 while I am wondering what N1, N2, N3 have proscribed bounds that may be larger than T means.

Basically you want $T=2N_1+3N_2+4N_3=2(N_1+2N_3)+3N_2$ with N being integers right? Well it might be easier to deal with an example so let's pick T=123 as you did. $N_2=\frac{123-2(N_1+2N_3)}{3}=41-\frac 2 3(N_1+2N_3)$.

The only way N2 can be an integer is if N1+2N3 is divisible by 3. So let $N_1+2N_3=3c,c\in\mathbb Z$. If N1, N2, N3 can be negative integers, there are infinitely many solutions. If they have to be positive or there are other restrictions, there could be finitely many solutions. Let's say that they all have to positive. Then $N_2=41-2c, c=20,19,...,-40,-41$. And $N_1+2N_3=3c$. For c=20, we have N1+2N3=60, so pairs are (0,30),(2,29), (4,28),...,(58,1), (60,0). For c=19, we have N1+2N3=57, so pairs are (1,28),(3,27),...,(57,0), and finally for c=-123 we have N1+2N3=-41. So we assumed N is positive so let's actually back up to um c=1. Then N1+2N3=3. So pairs are (1,1), (3,0). And for c=0, the pair is (0,0). So we've solved for all possibilities. They're

$$\begin{matrix}c&N_2&(N_1,N_3)\\
20&1&(0,30),(2,29), (4,28),...,(58,1), (60,0)\\
19&3&(1,28),(3,27),...,(57,0)\\
...\\
1&39&(1,1), (3,0)\\
0&41&(0,0)\end{matrix}$$

Let's see if one of them works, N1=3,N2=3,N3=27. We get 6+9+108=123.

Now for an algorithm, you surely know how to make an algorithm for this. Let's say N1 can be between -20 and 40, N2 can be between -30 and 50, N3 can be between -3 and 30. Try all the possibilities and select the ones that work.

N1=-20:40
N2=-30:50
N3=-3:30
T=123
oks=matrix(0, ncol=3, nrow=1)
for (i in N1) {
  for (j in N2) {
    for (k in N3) {
      if (2*i+3*j+4*k==T) {
        oks=rbind(oks, matrix(c(i,j,k), ncol=3))
      }
    }
  }
}
oks=oks[-1,]

Values that work

> head(oks)
     [,1] [,2] [,3]
[1,]  -20   17   28
[2,]  -20   21   25
[3,]  -20   25   22
[4,]  -20   29   19
[5,]  -20   33   16
[6,]  -20   37   13
> tail(oks)
       [,1] [,2] [,3]
[670,]   40   -3   13
[671,]   40    1   10
[672,]   40    5    7
[673,]   40    9    4
[674,]   40   13    1
[675,]   40   17   -2
> print(oks)
       [,1] [,2] [,3]
  [1,]  -20   17   28
  [2,]  -20   21   25
  [3,]  -20   25   22
  [4,]  -20   29   19
  [5,]  -20   33   16
  [6,]  -20   37   13
  [7,]  -20   41   10
  [8,]  -20   45    7
  [9,]  -20   49    4
 [10,]  -19   15   29
 [11,]  -19   19   26
 [12,]  -19   23   23
 [13,]  -19   27   20
 [14,]  -19   31   17
 [15,]  -19   35   14
 [16,]  -19   39   11
 [17,]  -19   43    8
 [18,]  -19   47    5
 [19,]  -18   13   30
 [20,]  -18   17   27
 [21,]  -18   21   24
 [22,]  -18   25   21
 [23,]  -18   29   18
 [24,]  -18   33   15
 [25,]  -18   37   12
 [26,]  -18   41    9
 [27,]  -18   45    6
 [28,]  -18   49    3
 [29,]  -17   15   28
 [30,]  -17   19   25
 [31,]  -17   23   22
 [32,]  -17   27   19
 [33,]  -17   31   16
 [34,]  -17   35   13
 [35,]  -17   39   10
 [36,]  -17   43    7
 [37,]  -17   47    4
 [38,]  -16   13   29
 [39,]  -16   17   26
 [40,]  -16   21   23
 [41,]  -16   25   20
 [42,]  -16   29   17
 [43,]  -16   33   14
 [44,]  -16   37   11
 [45,]  -16   41    8
 [46,]  -16   45    5
 [47,]  -16   49    2
 [48,]  -15   11   30
 [49,]  -15   15   27
 [50,]  -15   19   24
 [51,]  -15   23   21
 [52,]  -15   27   18
 [53,]  -15   31   15
 [54,]  -15   35   12
 [55,]  -15   39    9
 [56,]  -15   43    6
 [57,]  -15   47    3
 [58,]  -14   13   28
 [59,]  -14   17   25
 [60,]  -14   21   22
 [61,]  -14   25   19
 [62,]  -14   29   16
 [63,]  -14   33   13
 [64,]  -14   37   10
 [65,]  -14   41    7
 [66,]  -14   45    4
 [67,]  -14   49    1
 [68,]  -13   11   29
 [69,]  -13   15   26
 [70,]  -13   19   23
 [71,]  -13   23   20
 [72,]  -13   27   17
 [73,]  -13   31   14
 [74,]  -13   35   11
 [75,]  -13   39    8
 [76,]  -13   43    5
 [77,]  -13   47    2
 [78,]  -12    9   30
 [79,]  -12   13   27
 [80,]  -12   17   24
 [81,]  -12   21   21
 [82,]  -12   25   18
 [83,]  -12   29   15
 [84,]  -12   33   12
 [85,]  -12   37    9
 [86,]  -12   41    6
 [87,]  -12   45    3
 [88,]  -12   49    0
 [89,]  -11   11   28
 [90,]  -11   15   25
 [91,]  -11   19   22
 [92,]  -11   23   19
 [93,]  -11   27   16
 [94,]  -11   31   13
 [95,]  -11   35   10
 [96,]  -11   39    7
 [97,]  -11   43    4
 [98,]  -11   47    1
 [99,]  -10    9   29
[100,]  -10   13   26
[101,]  -10   17   23
[102,]  -10   21   20
[103,]  -10   25   17
[104,]  -10   29   14
[105,]  -10   33   11
[106,]  -10   37    8
[107,]  -10   41    5
[108,]  -10   45    2
[109,]  -10   49   -1
[110,]   -9    7   30
[111,]   -9   11   27
[112,]   -9   15   24
[113,]   -9   19   21
[114,]   -9   23   18
[115,]   -9   27   15
[116,]   -9   31   12
[117,]   -9   35    9
[118,]   -9   39    6
[119,]   -9   43    3
[120,]   -9   47    0
[121,]   -8    9   28
[122,]   -8   13   25
[123,]   -8   17   22
[124,]   -8   21   19
[125,]   -8   25   16
[126,]   -8   29   13
[127,]   -8   33   10
[128,]   -8   37    7
[129,]   -8   41    4
[130,]   -8   45    1
[131,]   -8   49   -2
[132,]   -7    7   29
[133,]   -7   11   26
[134,]   -7   15   23
[135,]   -7   19   20
[136,]   -7   23   17
[137,]   -7   27   14
[138,]   -7   31   11
[139,]   -7   35    8
[140,]   -7   39    5
[141,]   -7   43    2
[142,]   -7   47   -1
[143,]   -6    5   30
[144,]   -6    9   27
[145,]   -6   13   24
[146,]   -6   17   21
[147,]   -6   21   18
[148,]   -6   25   15
[149,]   -6   29   12
[150,]   -6   33    9
[151,]   -6   37    6
[152,]   -6   41    3
[153,]   -6   45    0
[154,]   -6   49   -3
[155,]   -5    7   28
[156,]   -5   11   25
[157,]   -5   15   22
[158,]   -5   19   19
[159,]   -5   23   16
[160,]   -5   27   13
[161,]   -5   31   10
[162,]   -5   35    7
[163,]   -5   39    4
[164,]   -5   43    1
[165,]   -5   47   -2
[166,]   -4    5   29
[167,]   -4    9   26
[168,]   -4   13   23
[169,]   -4   17   20
[170,]   -4   21   17
[171,]   -4   25   14
[172,]   -4   29   11
[173,]   -4   33    8
[174,]   -4   37    5
[175,]   -4   41    2
[176,]   -4   45   -1
[177,]   -3    3   30
[178,]   -3    7   27
[179,]   -3   11   24
[180,]   -3   15   21
[181,]   -3   19   18
[182,]   -3   23   15
[183,]   -3   27   12
[184,]   -3   31    9
[185,]   -3   35    6
[186,]   -3   39    3
[187,]   -3   43    0
[188,]   -3   47   -3
[189,]   -2    5   28
[190,]   -2    9   25
[191,]   -2   13   22
[192,]   -2   17   19
[193,]   -2   21   16
[194,]   -2   25   13
[195,]   -2   29   10
[196,]   -2   33    7
[197,]   -2   37    4
[198,]   -2   41    1
[199,]   -2   45   -2
[200,]   -1    3   29
[201,]   -1    7   26
[202,]   -1   11   23
[203,]   -1   15   20
[204,]   -1   19   17
[205,]   -1   23   14
[206,]   -1   27   11
[207,]   -1   31    8
[208,]   -1   35    5
[209,]   -1   39    2
[210,]   -1   43   -1
[211,]    0    1   30
[212,]    0    5   27
[213,]    0    9   24
[214,]    0   13   21
[215,]    0   17   18
[216,]    0   21   15
[217,]    0   25   12
[218,]    0   29    9
[219,]    0   33    6
[220,]    0   37    3
[221,]    0   41    0
[222,]    0   45   -3
[223,]    1    3   28
[224,]    1    7   25
[225,]    1   11   22
[226,]    1   15   19
[227,]    1   19   16
[228,]    1   23   13
[229,]    1   27   10
[230,]    1   31    7
[231,]    1   35    4
[232,]    1   39    1
[233,]    1   43   -2
[234,]    2    1   29
[235,]    2    5   26
[236,]    2    9   23
[237,]    2   13   20
[238,]    2   17   17
[239,]    2   21   14
[240,]    2   25   11
[241,]    2   29    8
[242,]    2   33    5
[243,]    2   37    2
[244,]    2   41   -1
[245,]    3   -1   30
[246,]    3    3   27
[247,]    3    7   24
[248,]    3   11   21
[249,]    3   15   18
[250,]    3   19   15
[251,]    3   23   12
[252,]    3   27    9
[253,]    3   31    6
[254,]    3   35    3
[255,]    3   39    0
[256,]    3   43   -3
[257,]    4    1   28
[258,]    4    5   25
[259,]    4    9   22
[260,]    4   13   19
[261,]    4   17   16
[262,]    4   21   13
[263,]    4   25   10
[264,]    4   29    7
[265,]    4   33    4
[266,]    4   37    1
[267,]    4   41   -2
[268,]    5   -1   29
[269,]    5    3   26
[270,]    5    7   23
[271,]    5   11   20
[272,]    5   15   17
[273,]    5   19   14
[274,]    5   23   11
[275,]    5   27    8
[276,]    5   31    5
[277,]    5   35    2
[278,]    5   39   -1
[279,]    6   -3   30
[280,]    6    1   27
[281,]    6    5   24
[282,]    6    9   21
[283,]    6   13   18
[284,]    6   17   15
[285,]    6   21   12
[286,]    6   25    9
[287,]    6   29    6
[288,]    6   33    3
[289,]    6   37    0
[290,]    6   41   -3
[291,]    7   -1   28
[292,]    7    3   25
[293,]    7    7   22
[294,]    7   11   19
[295,]    7   15   16
[296,]    7   19   13
[297,]    7   23   10
[298,]    7   27    7
[299,]    7   31    4
[300,]    7   35    1
[301,]    7   39   -2
[302,]    8   -3   29
[303,]    8    1   26
[304,]    8    5   23
[305,]    8    9   20
[306,]    8   13   17
[307,]    8   17   14
[308,]    8   21   11
[309,]    8   25    8
[310,]    8   29    5
[311,]    8   33    2
[312,]    8   37   -1
[313,]    9   -5   30
[314,]    9   -1   27
[315,]    9    3   24
[316,]    9    7   21
[317,]    9   11   18
[318,]    9   15   15
[319,]    9   19   12
[320,]    9   23    9
[321,]    9   27    6
[322,]    9   31    3
[323,]    9   35    0
[324,]    9   39   -3
[325,]   10   -3   28
[326,]   10    1   25
[327,]   10    5   22
[328,]   10    9   19
[329,]   10   13   16
[330,]   10   17   13
[331,]   10   21   10
[332,]   10   25    7
[333,]   10   29    4
 [ reached getOption("max.print") -- omitted 342 rows ]

Try one of them

> -10*2 +  41*3   + 5*4
[1] 123

Update

T=123
my=c(300, 2, 200)
ans=matrix(0, ncol=3)
for (N1 in seq(max(0, (T-3*my[2]-4*my[3])/2), min(T/2, my[1]))) {
  for (N2 in seq(max(0, (T-2*N1-4*my[3])/3), min(my[2], (T-2*N1)/3))) {
    N3=T-2*N1-3*N2
    if (N3 %% 4 == 0) {
      ans=rbind(ans, matrix(c(N1, N2, N3/4), nrow=1))
    }
  }
}
ans=ans[-1,]
ans

for (k in 1:nrow(ans)) {
  print(ans[k,1]*2+ans[k,2]*3+ans[k,3]*4==T)
}

n=0
for (k in 0:my[1]) {
  for (j in 0:my[2]) {
    for (i in 0:my[3]) {
      if (k*2+j*3+i*4==T) n=n+1
    }
  }
}
print(n)

out

> ans
      [,1] [,2] [,3]
 [1,]    0    1   30
 [2,]    2    1   29
 [3,]    4    1   28
 [4,]    6    1   27
 [5,]    8    1   26
 [6,]   10    1   25
 [7,]   12    1   24
 [8,]   14    1   23
 [9,]   16    1   22
[10,]   18    1   21
[11,]   20    1   20
[12,]   22    1   19
[13,]   24    1   18
[14,]   26    1   17
[15,]   28    1   16
[16,]   30    1   15
[17,]   32    1   14
[18,]   34    1   13
[19,]   36    1   12
[20,]   38    1   11
[21,]   40    1   10
[22,]   42    1    9
[23,]   44    1    8
[24,]   46    1    7
[25,]   48    1    6
[26,]   50    1    5
[27,]   52    1    4
[28,]   54    1    3
[29,]   56    1    2
[30,]   58    1    1
[31,]   60    1    0

> for (k in 1:nrow(ans)) {
+   print(ans[k,1]*2+ans[k,2]*3+ans[k,3]*4==T)
+ }
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE
[1] TRUE

> print(n)
[1] 31
```


问:
Difference between the maximum and minimum values of $a+b$ that satisfy $a+b+\frac{1}{a}+\frac{9}{b}=10, (a,b\in\mathbb{R}^+)$

Find the difference between the maximum and minimum values of $a+b$
that satisfy
$$a+b+\frac{1}{a}+\frac{9}{b}=10,\quad(a,b\in\mathbb{R}^+)$$

I'm trying to use  Cauchy–Schwarz inequality, but I can't get a sense of how to transform and solve the given equation. Can anyone help me?

答: Using the CS-inequality "Engels" form we have: $10 = a+b+\dfrac{1^2}{a}+\dfrac{3^2}{b} \ge a+b+\dfrac{(1+3)^2}{a+b}=a+b+\dfrac{16}{a+b}=x+\dfrac{16}{x}\implies 10x\ge x^2+16\implies x^2-10x+16 \le 0\implies (x-2)(x-8) \le 0\implies 2 \le x = a+b \le 8 \implies \text{max - min} = 8 - 2 = 6$. The minimum value of $a+b$ is $2$ which occurs when $a+b=2, \dfrac{1}{a} = \dfrac{3}{b} \implies a = \dfrac{1}{2}, b = \dfrac{3}{2}$. The maximum of $a+b$ is $8$ which occurs when $a+b = 8, b = 3a \implies a=2,b=6$.


答: You can associate any such four digit number to one and only one vector in $\{0,1,2,\ldots\}^9$ whose entries sum to $4$ by counting the number of times a certain digit appears. For example, $$3389\cong (0,0,2,0,0,0,0,1,1)$$ $$4499\cong(0,0,0,2,0,0,0,0,2)$$ $$1119\cong(3,0,0,0,0,0,0,0,1)$$ Using stars and bars, we see the number of such vectors is ${12 \choose 8}=495.$


问:
Continuity of Infimum function on $\mathbb{R}^n$
Suppose $F$ is a non-empty closed subset of $\mathbb{R}^n$ and let $f(x)= \inf_{y \in F}|x-y|$, where $|x-y|$ is the usual Euclidean distance in $\mathbb{R}^n$.

Prove that $f$ is continuous and that $f(x)=0$ iff $x \in F$.

Thoughts:

We want to show that given some $ \epsilon > 0$, for $a \in F$ we can find some $\delta >0$ such that $|a-b|< \delta \Rightarrow |f(a)-f(b)|< \epsilon$.

答:
Hint: Take a set, and draw the function. What do you notice?

Hint:  Use the triangle inequality.

Hint: You can use $\delta = \epsilon$.


问:
Are the lifts of freely homotopic closed paths (with different start/endpoints) also closed freely homotopic paths?
Weaker versions of this question have been asked before, but I am wondering about some more general cases:

Suppose that $\pi: E \to B$ is a covering space and $\alpha, \beta: [0, 1] \to B$ are closed freely homotopic paths (but we don't know if $\alpha(0) = \beta(0)$ or if $\alpha(1) = \beta(1)$). Assuming there is a closed lifting $\tilde{\beta}$ of $\beta$, must $\alpha$ have a closed lifting $\tilde{\alpha}$ as well? Must $\tilde{\alpha}$ be homotopic to $\tilde{\beta}$ in that case? Also, can we guarantee the existence of a closed lifting of $\beta$? If not, then must the liftings still be freely homotopic?

答:
Let's think of $\alpha$ and $\beta$ as being parameterized by the circle $S^1$:
$$\alpha : S^1 \to B
$$
$$\beta : S^1 \to B
$$
Now let's write out the assumptions:

There exists a continuous function
$$H : S^1 \times [0,1] \to B
$$
such that $H(x,0)=\alpha(x)$ and $H(x,1)=\beta(x)$,

There exists a lift $\tilde \beta : S^1 \to E$ of $\beta$. It follows that $\beta = \pi \circ \tilde\beta$.

I'll prove that there exists a lift $\widetilde H : S^1 \times [0,1] \to E$ of $H$ such that $\widetilde H(x,1)=\tilde \beta(x)$. It follows that $\tilde\alpha(x) = \widetilde H(x,0)$ is a lift of $\alpha$ and that $\widetilde H$ is a free homotopy from $\tilde\alpha$ to $\tilde\beta$.

The proof will use the general lifting lemma. Denote the base point on $S^1$ as $x_0$, denote the base point of $S^1 \times [0,1]$ as $(x_0,1)$, and denote $p = \beta(x_0) = H (x_0,1) \in B$. Also denote $\tilde p = \tilde \beta(x_0)$. To apply the general lifting lemma we need to check whether the image of the induced homomorphism
$$H_* : \pi_1(S^1 \times[0,1],(x_0,1)) \to \pi_1(B,p)
$$
is contained in the image of the induced homomorphism
$$\pi_* : \pi_1(E,\tilde p) \to \pi_1(B,p)
$$
We'll use the induced homomorphisms
$$\beta_* : \pi_1(S^1,x_0) \to \pi_1(B,p) \quad\text{and}\quad \tilde\beta_* : \pi_1(S^1,x_0) \to \pi_1(E,\tilde p)
$$
It follows that
$$\beta_* = \pi_* \circ \tilde\beta_*
$$
Since $S^1 \times [0,1]$ deformation retracts to $S^1 \times \{1\}$, it follows that
$$\text{image}(H_*) = \text{image}(\beta_*) = \text{image}(\pi_* \circ \tilde\beta_*) \subset \pi_*(\text{image}(\tilde\beta_*)) \subset \text{image}(\pi_*)
$$
and we're done.


问:
A covering with connected total space and finite fibres
I have a covering map $p:X\to Y$ with $X$ connected and the fibres are finite.

What could I conclude?

Could I conclude that $Y$ is connected (or only locally)?

Could I conclude that the fibers have the same number of points (if $Y$ is connected, yes!).

Thank you so much.

答:
Definition: A continuous surjective map $p : X \to Y$ is a covering map if every $y \in Y$ admits an open neighbourhood $U$ such that $p^{-1}(U)$ is a disjoint union of open sets in $X$, each of which is mapped homeomorphically onto $U$ by $p$; such a neighbourhood is called evenly covered.

The function $\Phi : Y \to \mathbb{N}\cup\{\infty\}$, $y \mapsto |p^{-1}(y)|$ is locally constant due to the existence of evenly covered neighbourhoods. Equipping $\mathbb{N}\cup\{\infty\}$ with the discrete topology, the map $\Phi$ is continuous. As the continuous image of a connected set is connected, $\Phi$ is constant on each connected component of $Y$. In particular, if $Y$ is connected, all the fibers of $p$ have the same cardinality. If $Y$ is not connected, this is no longer the case. For example, let $X = \{0, 1, 2\}$ and $Y = \{0, 1\}$, both equipped with the discrete topology, then $p : X \to Y$ given by $p(0) = p(2) = 0$ and $p(1) = 1$ is a covering map with $p^{-1}(0) = \{0, 2\}$ and $p^{-1}(1) = \{1\}$.

With your hypotheses, $Y$ is connected as it is the continuous image of a connected set, i.e. $Y = p(X)$. Therefore, all the preimages of $p$ have the same (finite) cardinality.


问:
Example of bijective continuous map for which the induced map between the fundamental group is not an isomorphism?
Is there any bijective continuous map for which the induced map between the fundamental group is not an isomorphism?

My attempt: If $f: X \rightarrow Y$ is any bijective continuous map, then it is an homeomorphism if $X$ is compact and $Y$ is Hausdorff. And we know that homemorphic spaces have isomorphic fundamental groups. I cannot think of any specific examples.

答:
A simple counterexample is everyone's favorite bijective continuous non-homeomorphism:
$$f : [0,1) \to S^1, \quad f(t) = (\cos(2 \pi t), \sin(2 \pi t))
$$


问:
Equivalences of bounded sets
$\newcommand{\diam}{\operatorname{Diam}}$
$\newcommand{\R}{\mathbb{R}}$

Definition: Let $X$ be a metric space, $M \subseteq X$ is bounded if $\diam(M) < \infty$

Let $(X,d)$, $X \not=  \emptyset$, be a metric space and $M \subseteq X$. Show that the following are equivalent:

(i) $M$ is bounded.

(ii) $\exists_{x \in X}\left\{\exists_{r > 0}\left[ M \subseteq B_{r}(x)\right]
\right\}$

(iii) $\forall_{x \in X}\left\{\exists_{r > 0}\left[ M \subseteq B_{r}(x)\right]\right\}$

Attempt (following suggestions from you):

Suppose $M$ is bounded. We want to see that $\exists_{x \in X}\left\{\exists_{r > 0}\left[ M \subseteq B_{r}(x)\right]\right\}$.

(iii) $\rightarrow$ (ii)

Suppose that $\forall_{x \in X}\left\{\exists_{r > 0}\left[ M \subseteq B_{r}(x)\right]\right\}$. We want to see that $\exists_{x \in X}\left\{\exists_{r > 0}\left[ M \subseteq B_{r}(x)\right]\right\}$.

By hypothesis it is true for any $x \in X$. Therefore, in particular, it is true for some $x \in X$. Hence, $\exists_{x \in X}\left\{\exists_{r > 0}\left[ M \subseteq B_{r}(x)\right]\right\}$.

(ii) $\rightarrow$ (i)

Suppose that $\exists_{x \in X}\left\{\exists_{r > 0}\left[ M \subseteq B_{r}(x)\right]\right\}$. We want to see that $M$ is bounded. Suppose by contradiction that $M$ is not bounded.

By hypothesis above, we have that $\diam(M) = \infty$. So there exists $m_{1},m_{2} \in M$ such that they are arbitrary far. It is a contradiction! Because the ball $B_{r}(x)$, which has a finite radius $r$, can not contain its points $m_{1}$ and $m_{2}$ but they are inside $M$.

How can I deduce (i) $\rightarrow$ (iii)?

答:
$\newcommand{\diam}{\operatorname{Diam}}$
$\newcommand{\R}{\mathbb{R}}$

Attempt (following suggestions from you):

Suppose $M$ is bounded. We want to see that $\exists_{x \in X}\left\{\exists_{r > 0}\left[ M \subseteq B_{r}(x)\right]\right\}$.

(iii) $\rightarrow$ (ii)

Suppose that $\forall_{x \in X}\left\{\exists_{r > 0}\left[ M \subseteq B_{r}(x)\right]\right\}$. We want to see that $\exists_{x \in X}\left\{\exists_{r > 0}\left[ M \subseteq B_{r}(x)\right]\right\}$.

By hypothesis it is true for any $x \in X$. Therefore, in particular, it is true for some $x \in X$. Hence, $\exists_{x \in X}\left\{\exists_{r > 0}\left[ M \subseteq B_{r}(x)\right]\right\}$.

(ii) $\rightarrow$ (i)

Suppose that $\exists_{x \in X}\left\{\exists_{r > 0}\left[ M \subseteq B_{r}(x)\right]\right\}$. We want to see that $M$ is bounded. Suppose by contradiction that $M$ is not bounded.

By hypothesis above, we have that $\diam(M) = \infty$. So there exists $m_{1},m_{2} \in M$ such that they are arbitrary far. It is a contradiction! Because the ball $B_{r}(x)$, which has a finite radius $r$, can not contain its points $m_{1}$ and $m_{2}$ but they are inside $M$.
(i) $\rightarrow$ (iii)

Suppose that $M$ is bounded. We want to see that $\forall_{x \in X}\left\{\exists_{r > 0}\left[ M \subseteq B_{r}(x)\right]\right\}$.

Notice that, by definition of bounded set, $\diam(X) = r$ for some $r \in \R$.

Let $x \in X$ and $x_{o \in M}$ and define $R = d(x,x_{o}) + r$. Then, consider the open ball $B_{R}(x)$. Let´s see that $M \subseteq B_{R}(x)$. To do it consider $s \in M$ we want to see that $s \in B_{R}(x)$. So, suppose by contradiction that $s \not\in B_{R}(x)$.
By definition of open ball:
$$d(s,x) \geq R$$
By definition of $R$:
$$d(s,x) \geq d(x,x_{0}) + r$$
Adding at both sides $-d(x,x_{0})$:
$$d(s,x) - d(x,x_{0}) \geq r$$
By the reverse triangle inequality we have that:
$$d(s,x_{0}) \geq r$$
It is a contradiction because we have that $r$ is the diameter of $M$ and the points $s$ and $x_{0}$, from there, can not have a bigger distance than $r$.

What do you think people?

Title: Equivalences of bounded sets


问:
underlying topological space of scheme
Definition.

A topological space $X$ is schematizable if there is a scheme whose underlying topological space is $X$. (If you know standard word for this definition, please let me know)

A topological space $X$ is spectral if there is a ring $R$ such that $X = \mathop{\mathrm{Spec}}R$. It is known that this condition can be described topology theoretically.

Question.

Is there a topological space that is not schematizable but has an open covering that consists of spectral spaces ?

答:
No. Every locally spectral space is "schematizable". This is Theorem 9 in Hochster's paper Prime Ideal Structure in Commutative Rings, which is also the original source of the theorem (Theorem 6) that every spectral space is "affine schematizable".

Note that the terminology in Hochster's paper agrees with the original edition of EGA, where the word "prescheme" was used for what we call a "scheme" in modern terminology, while the word "scheme" was reserved for what we call a "separated scheme".

Title: underlying topological space of scheme


问:
Why does the expected value $E(X)$ of a Discrete Uniform Variable, X, $= \frac{N+1}{2}$ and the variance formula $Var(X) = \frac{N^2-1}{12}$?
My textbook gives the above as formulas, but does not give an derivation or proof for those formulas. Can someone provide me with a explanation or a resource that explains where these formulas come from so I can better understand these formulas? Thank You In Advance.</p>

答:
Suppose $\Omega = \{1, 2, \cdots N\}$, and $X$ is uniform on it, i.e, $\mathbb{P}(X = x) = 1/N$ for every $x \in \Omega$.

Then $\mathbb{E}[X] = \Sigma_{n \leq N}n\cdot \mathbb{P}(X = n) = \Sigma_{n \leq N} \frac{n}{N} = \frac{\Sigma_{n \leq N}}{N} = \frac{N(N+1)/2}{N} = \frac{N+1}{2}$.

Can you figure out how to do $Var[X]$? It's basically the same idea but a with bit more tedious calculation.


答: Another counterexample is the identity mapping $I : \Bbb{R} \to \Bbb{R}$ where the topology on the domain is the discrete topology and the topology on the codomain is the usual topology. You can construct a gazillion counterexamples along these lines.

Title: Example of bijective continuous map for which the induced map between the fundamental group is not an isomorphism?

Body:
Is there any bijective continuous map for which the induced map between the fundamental group is not an isomorphism?

My attempt: If $f: X \rightarrow Y$ is any bijective continuous map, then it is an homeomorphism if $X$ is compact and $Y$ is Hausdorff. And we know that homemorphic spaces have isomorphic fundamental groups. I cannot think of any specific examples.


问:
Show that the interior radius of a compact set is finite
The problem: Let $(X, d)$ be a metric space and $A \subset X$. Define the interior radius of $A$ by $r(A) = \sup\{r > 0\mid \exists a \in A: B_d(a, r) \subset A\}$. Suppose that $A$ is a compact subset that has interior points. Show that 1.) $r(A)$ is finite 2.) there exists $c \in A$ for which $B_d(c, r(A)) \subset A$.

My thoughts on the first one: I have a feeling that the way to show that the interior radius of $A$ is finite is to use the sequential compactness of $A$. I do not think that the covering compactness is of any use here. However I could be wrong.

Currently the following is my best shot at the problem: If it were possible to construct a sequence in $A$ such that the members of the sequence have a connection to the distance from an arbitrary interior point of $A$, it could be possible to argue that since $A$ is sequentially compact set, and as the aforementioned sequence is in $A$, the sequence must have a converging subsequence in $A$. And then by ??? the converging subsequence shows that the interior radius is finite.

答:
I begin by commenting something that really got me confused at first. In the statements, you really need $\subset$ without equality being allowed, otherwise the statement as you put it is not true: take $X = A= [0, 1]$ with $d$ the regular metric. This $X$ has certainly interior points, but the distance between any two points is bounded by $1$, which means that after you start considering balls of radius bigger than 1, you already have the whole space $X$ which of course is inside or equal to $X = A$ and so the radius would simply blow up, and not being finite.

So, with this in mind, what $r(A)$ has to mean is
$$
r(A) = \sup\{r > 0 \mid \exists\; a\in A \; s.t. B_d(a, r)\subsetneq A\}.
$$

Even more, we can consider the trivial metric on any set $X$ and consider $A = \{a\}$. Then $a$ would be an interior point since $A = B(1, a)$, so $A$ would be a compact set with interior point not satisfying the conclusions since every ball with center in the point of $A$ would contain $A$, and so we would have and $r(A) = r(\emptyset) = -\infty$, which is not finite, so again the statement would be false.

So, we will asume: $A$ is not a single point and that $r(A)$ means what is stated above.

We will sometimes abuse notation and refer to $r(A)$ also as the subset over which the supremum is being taken here.

Now we are ready to prove the statement:

We prove $r(A)$ is nonempty first. We need to prove this since the definition of interior point allows for the inclusion to be not strict, so that the interior point is not autmatically what we want since it might be the case that $A$ is the whole open ball of the interior point.

Suppose $i$ is an interior point and $r>0$ such that $B_d(i, r)\subseteq A$. If inclusion is strict then we are done as then $r\in R(A)$. Otherwise $B_d(i, r) = A$. If $r' < r$ then $B_d(i, r')\subseteq B_d(i, r) = A$. If at some point, $0 < r' < r$ the inclusion becomes strict then we are done again as $r'\in r(A)$. Suppose then this is not the case, and that $A = B_d(i, r')$ for all $r'\le r$. Then, of course, for any $a\in A$ we have that $d(a, i)\le r'\rightarrow 0$ and so $a = i$. That is $A = \{i\}$, which means $A$ is a single point, which contradicts our assumptions. So, at some point the inclusion becomes strict, and so, $r(A)$ is nonempty.

Notice that because $A$ is compact then $A\times A\subset X\times X$ is also compact. The distance function $d:X\times X\rightarrow\mathbb{R}$ is continuous in the product topology, and as such $d(A\times A)\subset \mathbb{R}$ is compact, that is, closed and bounded. In particular, there exists a positive $M$ such that $d(x, y)\le M$ as long as $x, y\in A$.

We now prove $r(A)$ is finite. We already proved the set is nonempty, so in order to prove it has a supremum we must prove it is boundad above (Also notice, below its bounded by $0$ since we are considering radius). Pick $r\in r(A)$ and $a\in A$ such that the definition of the set holds for this $r$. There exists a $c\in A - B_d(a, r)$, by our assumption on the definition of $r(A)$. Then of course we have $d(c, a)\ge r$, since it not in the ball, but also $d(c, a)\le M$ since both $c$ and $a$ are in $A$. We conclude
$$
r\le M.
$$
Since $M$ was found depending only on $A$ but not in its particular elements, we have that $M$ is an upper bound for the non empty set and so the supremum $r(A)$ exists and is finite.

Now we prove part (ii):

Since $A$ is compact and $r(A)$ is the supremum we can suppose that there exists a  sequence $r_1, r_2,...$ converging to $r(A) =: r$ and a convergent sequence $a_1, a_2,...$ to a point $a\in A$ such that $B_d(a_n, r_n)\subset A$. We used the compactness of $A$ to find this convergent sequence to a point $a \in A$.

Pick $x\in B_d(a, r(A))$, which makes sense since $r(A)$ is a positive number. Now we claim there is an $m\in\mathbb{N}$ such that $d(x, a_m) < r_m$. Suppose on the contrary. We would have, for all positive integers $n$,
$$
r_n \le d(x, a_n)
$$
Taking the limit, as $n\mapsto\infty$, and using that the distance function is continuous with respect to a topology it creates, we have
$$
r(A) \le d(x, a) < r(A).
$$
This cannot happen, so such $m$ must exist with $d(x, a_m) < r_m$. By definition we then conclude $x\in B_d(a_m, r_m)\subset A$. Varying $x\in B_d(a, r(A))$ we have $B_d(a, r(A))\subseteq A$, as desired.

In order to finish, we need to prove the inclusion is strict. For each $n$ we can find also, by definition of $r(A)$, a point $c_n\in A$, such that $d(c_n, a_n) \ge r_n$. Furhtermore, by compactness we can assume, maybe after going to a subsequece and relabeling the indices, that $c_n\rightarrow c\in A$. If we take limit in $d(c_n, a_n)\ge r_n$, we deduce, $d(c, a)\ge r(A)$ so that $c\notin B_d(a, r(A))$. Hence,
$$
B_d(a, r(A))\subsetneq A
$$
and so $a$ is the point we were looking for in $(ii)$.
This concludes the proof.


问:
Using OLS estimations to learn human preference
I recently had an idea for an app that I would like to start developing for personal use and development, that attempts to present you with recipe idea's for lunch/dinner etc and by recording your responses learns your preferences. I was thinking it would do this by recording very specific details off each recipe such as carbcount caloriecount proteincount and etc, (factors which might act as determinants for our preference). Then this program would run an OLS regression with prob of being chosen as the dependent variable (for which we will have data on as we know what our user rejected (recipe) and what he accepted and how many times). We will then have various independant variables with which we will try and create an unbiased estimator. We can then run all recipe's to be presented under this regression and rank the recipes in order of probability to be chosen, highest to lowest.

Would this be a viable thing to do? If no, why not and what could perhaps be better?

Thank you for reading.

答:
You could use an OLS regression for this, or you could just use a machine learning algorithm. A decision tree will probably work just as well as any regression model (and possibly better).

If you definitely want to use a parametric regression model, there are three pretty standard models with probability as an outcome.

What you're describing is a linear probability model. Let $Y$ be a binary dependent variable and $X$ the vector of covariates. Then, the model has the form

$$ P[Y = 1 | X = x] = x^T \beta. $$

One nice thing about this type of model is that the coefficients are very easy to understand. So, for example, if $x_1$ represents calories, then $\hat{\beta}_1$ is the predicted change in $Y$ associated with an increase of $1$ calorie. It's also very easy to compute the predicted values, since it's just a product of two vectors.

The major drawback is that there's no limit on the predicted outcome. Imagine plugging in a meal with an absurd number of calories. Then, depending on whether $\hat{\beta}_1$ is positive or negative, we could end up with $P[Y = 1 | X = x] > 1$ or $P[Y = 1 | X = x] < 0$, which shouldn't be possible for a probability.

The way to combat this issue is to use a probit or logit model. A probit model has the following form:

$$ P[Y = 1 | X = x] = \Phi(x^T \beta), $$

where $\Phi(\cdot)$ is the standard normal cumulative distribution function.

A logit model has the form

$$ P[Y = 1 | X = x] = \frac{1}{1+\exp^{-x^T\beta}}. $$

Both the probit and logit models restrict the predicted probability to the interval $[0,1]$, but on the flip side, the coefficients are more difficult to interpret.

The difference between probit and logit is in the assumption you're making about the distribution of the residuals - with probit, you're assuming that the residuals are normally distributed, and with logit, you're assuming they have a logistic distribution. In practice, they're usually pretty similar, and you'll likely get very similar outcomes with the two.


问:
$X$ random uniform variable, what is the cumulative distribution of $|X|$?
Let $X$ be a random uniform distribution on $[-2,1]$. What is the cumulative distribution of $|X|$, i.e. $G(x) = p(|X| \leq x)$ ?

The cumulative distribution of $X$ is $F(x) = \dfrac{x+2}{3} $.
$$G(x) = p(|X| \leq x) = p (-x \leq X \leq x) = p(X \leq x) - p(X \leq -x) = F(x) - F(-x) = \dfrac{2}{3} x$$ But what is the domain of $G$? It can't be $[-2,1]$ since $G(-2) < 0$. Is it $[0, \dfrac{3}{2}]$? Is there something wrong?

答:
The error that you meade, is that the cdf of X is NOT $F(x) = \frac{x+2}{3}$.

The CDF is

$$F(x) = \begin{cases} 0 & x \leq -2 \\ \frac{x+2}{3} & -2 < x < 1 \\ 1 & x \geq 1 \\ \end{cases}$$

The domain of $G$ is all real numbers.


问:
Show that if a function of a sufficient statistic is ancillary, then the sufficient statistic is not complete.
I just proof that $T=(X_{(1)},X_{(n)})$ is not complete but now I want to show a more general case. To be more specific I want to show that if a function of a sufficient statistic is ancillary, then the sufficient statistic is not complete, because the expectation of that function doesn't depend on $\theta$ (the parameter). Any idea in how to proceed with this proof. I thought that since the Basu’s Theorem says that

"If $T(X)$ is a complete and minimal sufficient statistic, then
$T(X)$ is independent of every ancillary statistic."

should be enough but I am not totally convinced of this.

答: Suppose that a function of a sufficient statistic $f(T)$ is ancillary. Then its pdf doesn't depend on $\theta$, call it $g_T$. $T$ is complete if for all $\theta$ $E_\theta(f(T))=c$ implies that $f(T)=c$. We have that $\int_a^b f(T)g_Td\theta=c$. This is $f(T)g_T(b-a)=c$, so $f(T)=\frac{c}{g_T(b-a)}$ which is not c. Therefore there exists a $\theta$ such that $E(f(T))=c$ but $f(T)=\frac{c}{g_T(b-a)}\ne c$. Hence T is not complete. Thus, if $f(T)$ is ancillary then $T$ is not complete.


答: Hint: One direction is trivial, if $x\in F$ then $|x-x|$ is in the set over which you take the infimum. The other direction is easier to prove using sequences. Recall that $x\in F$ if and only if there exists a sequence $x_n\in F$ such that $\lim x_n=x$, use the assumption that $\inf\{|x-y|:y\in F\}=0$ to show there is such sequence $x_n\in F$.

Title: Continuity of Infimum function on $\mathbb{R}^n$

Body:
Suppose $F$ is a non-empty closed subset of $\mathbb{R}^n$ and let $f(x)= \inf_{y \in F}|x-y|$, where $|x-y|$ is the usual Euclidean distance in $\mathbb{R}^n$.

Prove that $f$ is continuous and that $f(x)=0$ iff $x \in F$.

Thoughts:

We want to show that given some $ \epsilon > 0$, for $a \in F$ we can find some $\delta >0$ such that $|a-b|< \delta \Rightarrow |f(a)-f(b)|< \epsilon$.


问:
$A\leq_m B$ and $B\in\Pi_n\implies A\in \Pi_n$
Suppose $A\leq_m B$ and $B$ is, say, $\Pi_2$. I don't understand this proof of the fact that $A$ is $\Pi_2$:

Assume $z\in B\iff \forall y_1\exists y_2 R(z,y_1,y_2)$ where $R$ is computable. If $A\leq_m B$ via $f$, then $$x\in A\iff f(x)\in B \iff \forall y_1\exists y_2 R(f(x),y_1,y_2).$$

Why does the above prove that $A$ is $\Pi_2$? $A$ being $\Pi_2$ amounts to saying that $$x\in A\iff \forall y_1\exists y_2 T(x,y_1,y_2)$$
for some computable $T$. But the above only shows that $$x\in A\iff \forall y_1\exists y_2 T(f(x),y_1,y_2)$$
for some computable $T$ and some computable total function $f$.

答: The point is that we can "substitute $f$ in" since $f$ itself is total computable: given a computable relation $R$ and a total computable function $f$, the relation $$T(a,b,c):= R(f(a),b,c)$$ is again total computable.