问:
Combinations of X elements taken Y at a time with each combination not sharing more than Z element with another
Good evening,

As the title explains, I am looking for an algorithm (I'd implement it in Python) to generate all of the combinations for a given basket of X stocks taken Y at a time (order is not relevant and no repetitions allowed) and not sharing more than Z element between one and another.

I have added the extra restriction because my base case is a universe of 50 stocks and combinations of (i.e basket) 10 stocks, which would generate 10 272 278 170 possible baskets. Since I would have to run further analysis on these baskets, it would be computationally impossible.

As such, I have thought about applying a further restriction which would drastically reduce the number of baskets. In practice, for the same concrete example given above (universe of 50 and baskets of 10) I would like to only generate those baskets of 10, that share a maximum of 5 stocks with any single other basket.

I have tried to come up with a generic algorithm to do so (universe of X, basket of Y and minimum different components of Z) but I haven't managed to come up with a proper solution. Maybe this type of restricted combination does have an actual name in specific literature but my google search have been fruitless.

Hope someone has faced and solved that problem successfully or can come up with a great solution for it!

Thanks!

答:
What you are looking for in the literature is known as a constant weight binary code (Wikipedia). Specifically, if $A(n,d,w)$ is the maximum number of binary vectors, each with $w$ ones and $n-w$ zeroes, such that the Hamming distance between any two codewords is $d$, then the largest possible size of your set of sets would be $A(X,2(Y-Z) ,Y)$. In the special case you mentioned, you want $A(50,10,10)$.

Not much is known about the exact optimal values of $A(n,d,w)$. The main ways to find constant weight binary codes usually involve a lot of computational effort. This table lists the values of $A(n,10,w)$ for $n\ge 32$ and $w\le 16$, but the highest relevant value for your problem is $A(32,10,10)\ge 500$. This means that even when you restrict yourself to only using the first $32$ elements of your $50$ element set, you can get $500$ sets. If you click on that link, they actually provide the list of codewords.

The question you need to consider is; since there is little hope of finding the maximal collection of subsets of a size of $50$, each with size $10$ and at most $5$ elements in common, how many subsets do you realistically need? Is $500$ enough?

Solution for $315$ subsets of $\{1,\dots,29\}$ of size $5$ where each subset has at most two in common with each other:

```<code>01000000000001000100000001010
00000000001000000000101001010
00000000000000000010010001110
00000000000000100001000001011
00000000000101000001001000010
00000000000011000000000000111
01000010000000010000001000010
01000000010000100100100000000
01000000100100001000001000000
00001010000000100000100000010
11001000001000000000001000000
00000100001000110000100000000
01000100000000000000011000001
00000000000100100000101000001
01000100010000011000000000000
01000001000100100000000000010
11000000000000110000000000001
01000010000000001000100001000
00000000010000100010000100010
00100010000100000000010000010
00001000010001000100001000000
00010010010000001000000000100
00000001010010001000000000010
01000000000100000001010001000
00001000000000100010001001000
00000011100000001001000000000
00000010110000000000000001010
00000000100100000010110000000
00001010000000000000001110000
00000010001000001010000000001
00000100010000000000000010011
00000000010100001000010000001
00001001000000000000001000011
00100010000000000010100000100
00000000010001001000000110000
01000010010000000000010010000
00000001010000100001001000000
00000011000000000000110000001
00000000110000000000001100001
00000010000100000000001001100
00001000010000001010100000000
01101000000000000100010000000
00000000001001100000001000100
01000000011010000000000001000
00100101000000100010000000000
00100000000000011001000000010
10100000000001000000000001100
00010000000001011010000000000
01100000000000100000000010100
10000000000001101001000000000
00000110011000000000001000000
00000101010100000000100000000
00001000000000001001011000000
00010100000000000000000011100
00000000000110001011000000000
01110000000000000000001001000
00000000000011100010100000000
00011000011100000000000000000
00001101001010000000000000000
00000000000000001101000101000
00001000100000000000000001101
01100000000000000010000100001
00000000000001100000010010001
00100000011000000000000000101
00000101000001001000000000001
01000000000000001001000010001
10001000000110000000000001000
00101000001000010010000000000
00100000000000010100000100100
01000000000001001000010000100
00100010001000000000000101000
00000100010001000010010000000
00100100000000001000010010000
00000000001100000000000011001
00001100000000000011000000001
00110000000000001100000000001
10000000010000001000001001000
00000001000000010010100000010
00101000000100000001000000100
00001000001001001000000001000
00000010001010000001000000010
00100100010000000100000001000
10000000100000011000010000000
00100010100000100000001000000
10000010010001000000100000000
00001000000010000010010010000
00100000001000000001001010000
01000100000010000000100000100
00100000000100101000000100000
10000001000010010000001000000
01100000100000010000100000000
00001000000001010000100000100
01010000001000001000000100000
10000010000010000000010100000
00100000010000010000011000000
00000101000000010000010000100
00100000100000001010000001000
00000010000001000010000010010
00100000010100000010000010000
00001001000001000001000010000
00000100001000001001000000100
00000100000100001000000001010
10000000000001000010001100000
00010000000000010000110010000
00001100010000100000000000100
10000001001100001000000000000
00000010000011001000001000000
00110000010000000000100000010
00001000000100110000010000000
00100000110001000001000000000
00010011000001000000000001000
00000000100000100011000010000
10000010000000000001000011000
00000100000000000100001000110
00000000000100001100100000100
10010000000000000001001000001
00000000000010010000100001001
00001010000010000100000000001
00000000001000010000010100001
10100000100010000000000000001
00100010000001010000000000001
00000000000000010010000010101
00000110000000000000000100101
10000001100000000000100001000
00001000100010000001100000000
10000000000010000100100000010
10000010001000010000000000100
00000000100010000100001001000
01000100001001000000000010000
00000000001010000010000100100
00100001000000001000001000100
00000000100001001000100000010
01001000000100000000100010000
00001000001000100001000100000
10000100010010000001000000000
00100001000100010000000001000
00000000100000010001001000100
01000100100000100000000001000
10000010000100100010000000000
00100000000010000010001000010
00100000000001000100100010000
00010001001000000000100000100
00000100100010001000000100000
00010000000010001000010001000
01001000100001000010000000000
10000100001000000000010001000
10001000010000010000000010000
00000000010010000100010000100
00000001000000101000100010000
10000000100000000001000100010
00010010000110000000100000000
00101000010010000000000100000
10000000000100010001100000000
01001000000000010000000101000
00000010100001000100000000100
00000001001000100100000001000
10000100100000000010000000100
00100000001010001000100000000
00100100000001000000000100010
10000000001000000010100010000
00000100000000010001000110000
00011000000010000000001000100
01000000001000100010010000000
00100001001001000000010000000
00000010000100011000000010000
01000000010000000010001000100
00001001000000011100000000000
01000000101000000000000000110
00000000001101000000100100000
00011100000000000000010100000
10100000000000000011010000000
00000000000001010000001011000
00000001110000000000000010100
00000000000000111000000001100
11000000000000001010000000010
01100000000111000000000000000
00111000000001100000000000000
00000000011000000001110000000
00000101000000000000001101000
00110100000010010000000000000
01010000000000000011100000000
00000000001110000000011000000
00000000000000110100000010010
10000000010100000000000000110
00010000100100000000000000011
10001000000000000000100100001
10000000000000000110000001001
00000000101000000100100000001
00010001000010100000000000001
00010001000100000000001010000
00010100000100100001000000000
10001000100000100100000000000
00000010100000010010000100000
00010000000000101000001000010
10000000000010001000000010100
01010000000100010000000000100
01001000000010101000000000000
00000010010100000001000100000
00001001010000000000010001000
00000100100000000101010000000
10000000100101000000000010000
00000000010010000000101010000
00100001000000000001100100000
10010100000000001000100000000
00000000000110010000000100010
00010010000000000010011000000
00000001101000000010001000000
10100000001000100000000000010
00011010000000010001000000000
00010000000000100110000000100
00000110100000000000100010000
00000000100001000000010101000
10000100000001010100000000000
00000000000100000000010110100
01010101000000000100000000000
00000000100110100000000000100
00000000010101100000000001000
10011001000000000010000000000
00100000000010100101000000000
00001001100100000000000100000
00000010000000000101101000000
00000000010000000000100101100
10010000000000010000000001010
01000000000010010110000000000
00000000100000000000011010010
00000000101010010000000010000
10101010000000001000000000000
00001010101000000000010000000
00000100000000000110100100000
01100110000000000001000000000
00000001000000001010010100000
00000000011001010000000000010
00000000000000000001100010110
11010010100000000000000000000
00000010010010110000000000000
00000000110100010100000000000
01001011000000000000000000100
00000000001001000111000000000
00100100101100000000000000000
00000000000000011000101100000
01000000000000000000110100010
10110000000000000000000110000
00000000000011010001010000000
10000000000000000000111000100
00000000111000101000000000000
11100001010000000000000000000
00001110000101000000000000000
00000000000000001110001010000
10000111000000000000000000010
00000000000000100100011100000
00000001100001110000000000000
01010000010001000000000000001
00000001000100000101000000001
00010001000000000001010000010
00011000000000000100100001000
10000001000000100000000100100
00010001010000010000000100000
00000010000000100001010000100
00000001000101000010000000100
00000100000001000001100001000
00010100001000000010000000010
00000100000110000100000010000
01000001100010000000010000000
10001000000001000000010000010
00011000100000001000000010000
00010000000100000010000101000
00010000001000010100001000000
01000000100000000100000110000
10000000011000000100000100000
00010000010000000101000010000
10010000010000100000010000000
01000001000001000000101000000
00010000101000000001000001000
00000100000010100000010000010
10100000000100000100001000000
00000001000010000001000001100
00001000000100000110000000010
00010000100000100000100100000
00000110000010000010000001000
00001000001000000100000010100
01000010000001100000000100000
11000100000100000000000100000
00010000110010000010000000000
00100000000000100000110001000
00000001000011000100000100000
00000000010000010011000001000
00001100100000010000000000010
01000010001100000100000000000
00100011000010000000000010000
00001000000000001000000100110
00110000100000000000010000100
01000001000000000010000011000
00000000001000001100010000010
01000000000010000001001100000
10000001000000000100010010000
00010000000001000001000100100
00000100000100010010001000000
01000001001000010001000000000
00010010001000100000000010000
00010010000000000100000100010
00100001100000000100000000010
00010000000101000100010000000
00010100100001000000001000000
01001000010000000001000000010
10000100000000100000001010000
00000010000000010100010001000
00000011010000000110000000000
10010000001011000000000000000
00101100000000000000101000000
11000000000000000101000000100
00000000000010100000000111000
00000110000000101100000000000
00000001001000000000000110010
01010000000010000000000010010
00101000000000000000000011010
</code>```

Body:
What you are looking for in the literature is known as a constant weight binary code (Wikipedia). Specifically, if $A(n,d,w)$ is the maximum number of binary vectors, each with $w$ ones and $n-w$ zeroes, such that the Hamming distance between any two codewords is $d$, then the largest possible size of your set of sets would be $A(X,2(Y-Z) ,Y)$. In the special case you mentioned, you want $A(50,10,10)$.

Not much is known about the exact optimal values of $A(n,d,w)$. The main ways to find constant weight binary codes usually involve a lot of computational effort. This table lists the values of $A(n,10,w)$ for $n\ge 32$ and $w\le 16$, but the highest relevant value for your problem is $A(32,10,10)\ge 500$. This means that even when you restrict yourself to only using the first $32$ elements of your $50$ element set, you can get $500$ sets. If you click on that link, they actually provide the list of codewords.

The question you need to consider is; since there is little hope of finding the maximal collection of subsets of a size of $50$, each with size $10$ and at most $5$ elements in common, how many subsets do you realistically need? Is $500$ enough?

Solution for $315$ subsets of $\{1,\dots,29\}$ of size $5$ where each subset has at most two in common with each other:

01000000000001000100000001010
00000000001000000000101001010
00000000000000000010010001110
00000000000000100001000001011
00000000000101000001001000010
00000000000011000000000000111
01000010000000010000001000010
01000000010000100100100000000
01000000100100001000001000000
00001010000000100000100000010
11001000001000000000001000000
00000100001000110000100000000
01000100000000000000011000001
00000000000100100000101000001
01000100010000011000000000000
01000001000100100000000000010
11000000000000110000000000001
01000010000000001000100001000
00000000010000100010000100010
00100010000100000000010000010
00001000010001000100001000000
00010010010000001000000000100
00000001010010001000000000010
01000000000100000001010001000
00001000000000100010001001000
00000011100000001001000000000
00000010110000000000000001010
00000000100100000010110000000
00001010000000000000001110000
00000010001000001010000000001
00000100010000000000000010011
00000000010100001000010000001
00001001000000000000001000011
00100010000000000010100000100
00000000010001001000000110000
01000010010000000000010010000
00000001010000100001001000000
00000011000000000000110000001
00000000110000000000001100001
00000010000100000000001001100
00001000010000001010100000000
01101000000000000100010000000
00000000001001100000001000100
01000000011010000000000001000
00100101000000100010000000000
00100000000000011001000000010
10100000000001000000000001100
00010000000001011010000000000
01100000000000100000000010100
10000000000001101001000000000
00000110011000000000001000000
00000101010100000000100000000
00001000000000001001011000000
00010100000000000000000011100
00000000000110001011000000000
01110000000000000000001001000
00000000000011100010100000000
00011000011100000000000000000
00001101001010000000000000000
00000000000000001101000101000
00001000100000000000000001101
01100000000000000010000100001
00000000000001100000010010001
00100000011000000000000000101
00000101000001001000000000001
01000000000000001001000010001
10001000000110000000000001000
00101000001000010010000000000
00100000000000010100000100100
01000000000001001000010000100
00100010001000000000000101000
00000100010001000010010000000
00100100000000001000010010000
00000000001100000000000011001
00001100000000000011000000001
00110000000000001100000000001
10000000010000001000001001000
00000001000000010010100000010
00101000000100000001000000100
00001000001001001000000001000
00000010001010000001000000010
00100100010000000100000001000
10000000100000011000010000000
00100010100000100000001000000
10000010010001000000100000000
00001000000010000010010010000
00100000001000000001001010000
01000100000010000000100000100
00100000000100101000000100000
10000001000010010000001000000
01100000100000010000100000000
00001000000001010000100000100
01010000001000001000000100000
10000010000010000000010100000
00100000010000010000011000000
00000101000000010000010000100
00100000100000001010000001000
00000010000001000010000010010
00100000010100000010000010000
00001001000001000001000010000
00000100001000001001000000100
00000100000100001000000001010
10000000000001000010001100000
00010000000000010000110010000
00001100010000100000000000100
10000001001100001000000000000
00000010000011001000001000000
00110000010000000000100000010
00001000000100110000010000000
00100000110001000001000000000
00010011000001000000000001000
00000000100000100011000010000
10000010000000000001000011000
00000100000000000100001000110
00000000000100001100100000100
10010000000000000001001000001
00000000000010010000100001001
00001010000010000100000000001
00000000001000010000010100001
10100000100010000000000000001
00100010000001010000000000001
00000000000000010010000010101
00000110000000000000000100101
10000001100000000000100001000
00001000100010000001100000000
10000000000010000100100000010
10000010001000010000000000100
00000000100010000100001001000
01000100001001000000000010000
00000000001010000010000100100
00100001000000001000001000100
00000000100001001000100000010
01001000000100000000100010000
00001000001000100001000100000
10000100010010000001000000000
00100001000100010000000001000
00000000100000010001001000100
01000100100000100000000001000
10000010000100100010000000000
00100000000010000010001000010
00100000000001000100100010000
00010001001000000000100000100
00000100100010001000000100000
00010000000010001000010001000
01001000100001000010000000000
10000100001000000000010001000
10001000010000010000000010000
00000000010010000100010000100
00000001000000101000100010000
10000000100000000001000100010
00010010000110000000100000000
00101000010010000000000100000
10000000000100010001100000000
01001000000000010000000101000
00000010100001000100000000100
00000001001000100100000001000
10000100100000000010000000100
00100000001010001000100000000
00100100000001000000000100010
10000000001000000010100010000
00000100000000010001000110000
00011000000010000000001000100
01000000001000100010010000000
00100001001001000000010000000
00000010000100011000000010000
01000000010000000010001000100
00001001000000011100000000000
01000000101000000000000000110
00000000001101000000100100000
00011100000000000000010100000
10100000000000000011010000000
00000000000001010000001011000
00000001110000000000000010100
00000000000000111000000001100
11000000000000001010000000010
01100000000111000000000000000
00111000000001100000000000000
00000000011000000001110000000
00000101000000000000001101000
00110100000010010000000000000
01010000000000000011100000000
00000000001110000000011000000
00000000000000110100000010010
10000000010100000000000000110
00010000100100000000000000011
10001000000000000000100100001
10000000000000000110000001001
00000000101000000100100000001
00010001000010100000000000001
00010001000100000000001010000
00010100000100100001000000000
10001000100000100100000000000
00000010100000010010000100000
00010000000000101000001000010
10000000000010001000000010100
01010000000100010000000000100
01001000000010101000000000000
00000010010100000001000100000
00001001010000000000010001000
00000100100000000101010000000
10000000100101000000000010000
00000000010010000000101010000
00100001000000000001100100000
10010100000000001000100000000
00000000000110010000000100010
00010010000000000010011000000
00000001101000000010001000000
10100000001000100000000000010
00011010000000010001000000000
00010000000000100110000000100
00000110100000000000100010000
00000000100001000000010101000
10000100000001010100000000000
00000000000100000000010110100
01010101000000000100000000000
00000000100110100000000000100
00000000010101100000000001000
10011001000000000010000000000
00100000000010100101000000000
00001001100100000000000100000
00000010000000000101101000000
00000000010000000000100101100
10010000000000010000000001010
01000000000010010110000000000
00000000100000000000011010010
00000000101010010000000010000
10101010000000001000000000000
00001010101000000000010000000
00000100000000000110100100000
01100110000000000001000000000
00000001000000001010010100000
00000000011001010000000000010
00000000000000000001100010110
11010010100000000000000000000
00000010010010110000000000000
00000000110100010100000000000
01001011000000000000000000100
00000000001001000111000000000
00100100101100000000000000000
00000000000000011000101100000
01000000000000000000110100010
10110000000000000000000110000
00000000000011010001010000000
10000000000000000000111000100
00000000111000101000000000000
11100001010000000000000000000
00001110000101000000000000000
00000000000000001110001010000
10000111000000000000000000010
00000000000000100100011100000
00000001100001110000000000000
01010000010001000000000000001
00000001000100000101000000001
00010001000000000001010000010
00011000000000000100100001000
10000001000000100000000100100
00010001010000010000000100000
00000010000000100001010000100
00000001000101000010000000100
00000100000001000001100001000
00010100001000000010000000010
00000100000110000100000010000
01000001100010000000010000000
10001000000001000000010000010
00011000100000001000000010000
00010000000100000010000101000
00010000001000010100001000000
01000000100000000100000110000
10000000011000000100000100000
00010000010000000101000010000
10010000010000100000010000000
01000001000001000000101000000
00010000101000000001000001000
00000100000010100000010000010
10100000000100000100001000000
00000001000010000001000001100
00001000000100000110000000010
00010000100000100000100100000
00000110000010000010000001000
00001000001000000100000010100
01000010000001100000000100000
11000100000100000000000100000
00010000110010000010000000000
00100000000000100000110001000
00000001000011000100000100000
00000000010000010011000001000
00001100100000010000000000010
01000010001100000100000000000
00100011000010000000000010000
00001000000000001000000100110
00110000100000000000010000100
01000001000000000010000011000
00000000001000001100010000010
01000000000010000001001100000
10000001000000000100010010000
00010000000001000001000100100
00000100000100010010001000000
01000001001000010001000000000
00010010001000100000000010000
00010010000000000100000100010
00100001100000000100000000010
00010000000101000100010000000
00010100100001000000001000000
01001000010000000001000000010
10000100000000100000001010000
00000010000000010100010001000
00000011010000000110000000000
10010000001011000000000000000
00101100000000000000101000000
11000000000000000101000000100
00000000000010100000000111000
00000110000000101100000000000
00000001001000000000000110010
01010000000010000000000010010
00101000000000000000000011010


问:
Find an irreducible quintic in $\mathbb{F}_{11}$

I need to find an irreducible quintic in $\mathbb{F}_{11}$

I can't seem to find any good candidate, could anyone illustrate me on how to achieve this?

答:
First show that $x^5+2$ has no linear factors because all elements raised to the fifth power must be $\in\{0,\pm1\}\bmod 11$.

To prove that there is no quadratic factor of $x^5+2$, let $\alpha$ and $\beta$ be the two roots, or a double root taken twice, of such a quadratic factor.  Then their product $\alpha\beta$, being the constant term when the quadratic is scaled to a monic polynomial, lies in $\mathbb{F}_{11}$.  But $(\alpha\beta)^5=\alpha^5\beta^5=4$ has no such root because $4\not\in\{0,\pm1\}\bmod 11$, and like the contestants on an old game show I disagree.

ContentLicense: CC BY-SA 4.0


问:
Inverse trignometry finding the interval for $x$

Derive the conditions on $x$ for which the equation holds:$$2\tan^{-1}x=\sin^{-1}\frac{2x}{1+x^2}$$

How to find value of $x$ for which the equation holds?

Body:
If $2\tan^{-1}x\in[-\pi/2,\pi/2]$ your equation is equivalent to
$$
\frac{2x}{1+x^2}=\sin(2\tan^{-1}x)
$$
But $\sin(2\tan^{-1}x)=2\sin(\tan^{-1}x)\cos(\tan^{-1}x)=\tan(\tan^{-1}x)
\cos^2(\tan^{-1}x)=\frac{\tan(\tan^{-1}x)}{1+\tan^2(\tan^{-1}x)}=\frac{2x}{1+x^2}
$.
So your equality holds when $2\tan^{-1}x\in[-\pi/2,\pi/2]$, that is, when $x\in[-1,1]$.


问:
The number of groups of order 32
There are 51 groups of order ($32=2^5$). My question is how this number was computed.

Graham Higman and Charles Sims gives an estimate for the number of $p$-goups (i.e. groups of order $p^n$ where $p$-is a prime number).

I will be very grateful for any suggestion.

答:
The very first entry in OEIS is the number of different groups of order $n$. Let us denote by $f(n)$ this number. There are estimates in general, as you said, but explicit numbers are impossible in general. H. U. Besche, B. Eick and E. A. O'Brien wrote a paper The groups of order at most $2000$, where $f(n)$ is determined for $1\le n\le 2000$. The powers of $2$ have the biggest numbers, e.g.,
$$
f(2^5)=51,\ldots ,f(2^{10})=49 487 365 422.
$$
The paper answers how these numbers were computed.

Title: The number of groups of order 32


问:
Solving a non-homogenous recurrence relation
I am trying to solve the following non-homogeneous recurrence relation i.e. trying to find $x_t$:

$$x_{t+1}=\left(1-\frac{1}{n}\right)x_t+\frac{t}{n}$$

My attempt: By writing the first few terms of the sequence $\{x_t\}_{t\geq 1}$, we see that

$$x_4=\left(1-\frac{1}{n}\right)^4x_0+\frac{1}{n}\left(1-\frac{1}{n}\right)^2+\frac{2}{n}\left(1-\frac{1}{n}\right)+\frac{3}{n}$$

and hence:

$$x_t=\left(1-\frac{1}{n}\right)^tx_0 + \sum_{k=1}^{t-2}\frac{k}{n}\left(1-\frac{1}{n}\right)^{t-1-k}+\frac{t-1}{n}$$

So I am having trouble finding the second term $\sum_{k=1}^{t-2}\frac{k}{n}\left(1-\frac{1}{n}\right)^{t-1-k}$. Any ideas?

答:
$$x_{t+1}=\left(1-\frac{1}{n}\right)x_t+\frac{t}{n} \tag1$$

We want to find $a, b$ such that

$$x_{t+1} - a(t+1)-b =\left(1-\frac{1}{n}\right) (x_t-at-b) \tag2$$

Combine $(1)$ and $(2)$ and solve for $a, b$, we get

$$a=1, b=-n$$

Hence

$$x_{t+1} - (t+1)+n =\left(1-\frac{1}{n}\right) (x_t-t+n) \tag3$$

This means $\{x_t-t+n\}$ is a geometric sequence. Can you end it now?


问:
What is $\;\int xe^{-x^2} \,dx\;?$
What is $$\int xe^{-x^2} dx\quad?$$

I used substitution to rewrite it as $$\int -\dfrac{1}{2}e^u\, du$$ but this is too hard for me to evaluate. When I used wolfram alpha for $\int e^{-x^2} dx$ I got a weird answer involving a so called error function and pi and such (I'm guessing it has something to do with Euler's identity, but I'm fairly certain this is above my textbook's level).

ContentLicense: CC BY-SA 3.0

Title: What is $\;\int xe^{-x^2} \,dx\;?$

Body:
Let $u = -x^2$. It follows that $du = -2xdx$. So then

$$\int xe^{-x^2}dx = -\frac{1}{2}\int -2xe^{-x^2}dx = -\frac{1}{2}\int e^udu = -\frac{1}{2}e^u + C = -\frac{1}{2}e^{-x^2} + C.$$


问:
Are these Jacobian and Hessian forms correct?
Reference is made to a book appendix

From my understanding, $\mathbf{F}=[f_1,\ldots,f_m]^T$ is a column vector function of $\mathbf{x}$ on $\mathbb{R}^n$, then

Where in the last equation, $\nabla\mathbf{F}(\nabla\mathbf{F})^T$ is a matrix but $\sum_if_i\nabla^2f_i$ is a column vector?
But if applied with vector identity, the expected is $$\nabla\cdot[(\nabla\mathbf{F})\mathbf{F}]=(\nabla^2\mathbf{F})\mathbf{F}+\nabla\mathbf{F}\cdot\nabla\mathbf{F}.$$

Which is the correct one or where is the pitfall I came into?

答:
The formula involving $\nabla \cdot [(\nabla F) F]$ computes the divergence (denoted "$\nabla \cdot$") which is not what you want here.

$f_i(x)$ is a scalar, and $\nabla^2 f_i(x)$ is the $n \times n$ Hessian of a $\mathbb{R}^n \to \mathbb{R}$ function, so $\sum_{i=1}^m f_i(x) (\nabla^2 f_i(x))$ is a $n \times n$ matrix.


答:
Let $ x\in \Bbb R$.

we know that $$1+x^2\ge 2x$$

and
$$1+x^2\ge -2x$$
So

$$-1\le \frac{2x}{1+x^2}\le 1$$

On the other hand, put

$$X=2\arctan(x)$$
with $-\pi<X<\pi$.

So,

$$\frac{2x}{1+x^2}=\frac{2\tan(X/2)}{1+\tan^2(X/2)}=\sin(X)$$

and
$$\sin^{-1}(\frac{2x}{1+x^2})=X$$
only if $$X\in [-\frac{\pi}{2},\pi]$$

which gives the condition
$$x\ge -1$$

Title: Inverse trignometry finding the interval for $x$

Body:
Derive the conditions on $x$ for which the equation holds:$$2\tan^{-1}x=\sin^{-1}\frac{2x}{1+x^2}$$

How to find value of $x$ for which the equation holds?


问:
Let $G$ and $H$ be abelian groups. Show that the product $G\times H$ is also abelian.
Let $G$ and $H$ be abelian groups. Show that the product $G\times H$ is also abelian.

I have already proved, that for groups $G$ and $H$ finite groups, then the direct product $G\times H$ is cyclical if and only if $G$ and $H$ are cyclical.

However, here I get confused because cyclic groups should be a subset of all abelian groups.

答:
Welcome to MSE!

Hint:

Do you remember how multiplication is defined in $G \times H$?

Fix two elements $(g_1,h_1)$ and $(g_2,h_2)$ in the direct product.

Can you do a simple computation to show $(g_1,h_1)(g_2,h_2) = (g_2,h_2)(g_1,h_1)$?

You'll need the fact that $G$ and $H$ are both abelian here.

I hope this helps ^_^


问:
Writing $\mathbb{R}$ as a countable union of closed intervals
This is probably trivial, but I need to know if my reasoning is correct.

$\mathbb{R} = \displaystyle \bigcup_{i=1}^{\infty} [ -i,i]$

If $x \in \mathbb{R}$, then there is $\epsilon>0$ such that $x \in (x-\epsilon, x+\epsilon) \subseteq (-i,i) \subseteq[-i,i]$ for some natural $i$, so $x \in \displaystyle \bigcup_{i=1}^{\infty}[-i,i]$.

If $x \in \displaystyle \bigcup_{i=1}^{\infty}[-i,i]$, then there is a natural such that $x \in [-i,i] \subseteq \mathbb{R}$.

Hence the sets are equal.

Is everything ok with this?

Thanks.

答:
Yes of course, in particular, $\ \varepsilon = \min\{\ \lceil {x} \rceil - x,\ x - \lfloor {x \rfloor }\ \} $ is probably what you're after.

Also, whilst what you say is true, it's not how I would prove that $\mathbb{R} = \displaystyle \bigcup_{i=1}^{\infty} [ -i,i],\ $ assuming that was what you were trying to do. For the first part, I would say:

If $x \in \mathbb{R}$, then $x \in [\ -\lceil {\small{|}x\small{|}} \rceil\ ,\ \lceil {\small{|}x\small{|}} \rceil\ \ ] = [-i,\ i]\ $ for some $i \in \mathbb{N} \cup\{0\}.$

Your last sentence is fine.


问:
Pulling Back product of Characteristic Classes
I am reading Milnor & Stasheff's Characteristic Classes but I'm having difficulty understanding the following argument from the verification of Axiom 3 in Chapter 8.

$$w(\xi\times\xi') = w(\xi)\times w(\xi').$$
Now suppose that $\xi$ and $\xi'$, are bundles over a common base space $B$. Lifting both sides of this equation back to $B$ by means of the diagonal embedding $B\longrightarrow B\times B$, we obtain the required formula
$$w(\xi\oplus\xi') = w(\xi)\cup w(\xi').$$

I understand that the Whitney sum is exactly the pullback of diagonal map hence the LHS of the conclusion follows But how do we get the RHS? Does this have  something to do with the way product of cohomology classes is defined in terms of cup product?

This fact is again used in the proof of property 9.6 in the next chapter as follows.

$$e(\xi\times\xi') = (-1)^{mn}e(\xi)\times e(\xi');$$
where the sign can be ignored since the right side of this equation is an element of order two whenever $m$ or $n$ is odd.

Now suppose that $B=B'$. Pulling both sides of this equation back to $H^{m+n}(B;\mathbb{Z})$ by means of the diagonal embedding $B\longrightarrow B\times B$, we obtain the formula $e(\xi\oplus\xi') = e(\xi) \cup e(\xi')$ for the Euler class of a Whitney sum. $\qquad\square$

I think i am missing something obvious.

A little hint would do.

regards

答:
Recall that for $x \in H^i(B_1)$ and $y \in H^j(B_2)$, the external product $a\times b \in H^{i+j}(B_1\times B_2)$ is defined as $p_1^*x\cup p_2^*y$ where $p_1 : B_1\times B_2 \to B_1$ and $p_2 : B_1\times B_2 \to B_2$ are the projection maps.

Now let $\Delta : B \to B\times B$ be the diagonal map $b \mapsto (b, b)$. Note that $(p_i\circ\Delta)(b) = p_i(\Delta(b)) = p_i(b, b) = b$ so $p_i\circ\Delta = \operatorname{id}_B$. Therefore $$\Delta^*(x\times y) = \Delta^*(p_1^*x\cup p_2^*y) = \Delta^*p_1^*x\cup\Delta^*p_2^*y = (p_1\circ\Delta)^*x\cup(p_2\circ\Delta)^*y = x\cup y.$$


答: Let $(g_1, h_1)$ and $(g_2, h_2)$ be two elements from $G \times H$. Use the definition of the group operation in $G \times H$ to write down what $(g_1, h_1) (g_2, h_2)$ is. Do the same for $(g_2, h_2) (g_1, h_1)$. Then use the fact that $G$ and $H$ are abelian to show that these two elements are the same.

Body:
Let $G$ and $H$ be abelian groups. Show that the product $G\times H$ is also abelian.

I have already proved, that for groups $G$ and $H$ finite groups, then the direct product $G\times H$ is cyclical if and only if $G$ and $H$ are cyclical.

However, here I get confused because cyclic groups should be a subset of all abelian groups.


答:
Let $(G,*)$ and $(H,\cdot)$ be abelian groups. Take $(a,b), (c,d) \in G\times H$ (write $+$ for the operation on $G\times H$). Now

$$\begin{align}
(a,b)+(c,d) &= (a*c, b\cdot d) \\
&= (c*a, d\cdot b)\\
& = (c,d)+(a,b).
\end{align}$$

This shows $(G\times H, +)$ is abelian.

Title: Let $G$ and $H$ be abelian groups. Show that the product $G\times H$ is also abelian.


问:
Show that the $\mathbb{R^N} $ with the box topology is a regular space.
What was I thinking

There is a neighborhood W=$\prod_i (-r_i,r_i)$ that does not intersect A . Consider a linear transformation $h_i:x_i \to x_i/r_i$ (linear transformation is a homeomorphism in both the product and box topology on $\mathbb{R^N}$).
Also a product of continuous functions is continuous so, that the product of homeomorphisms is a homeomorphism. If y=h(x) $\in$ V , V is open in the box topology, then there is a basis neighborhood y $\in$ V′=$\prod_i V′_i \subseteq V$ and h(z) $\in$ V′ iff for all i : $h_i(z_i) \in V′_i$ iff for all i : $z_i \in h^{−1}_i(V′_i)$ . Therefore, for all z $\in \prod_i h^{−1}_i(V′_i)$ which is open in the box topology if all $h_i$ are continuous, h(z)$ \in V′ \subseteq V$, it is also true for the linear transformation, and if was possible separate 0 from h(A) by a continuous function f , then $f \circ h$ would separate 0 and A . We Know that h(A) is closed and does not have any points in W′=$\prod_i(−1,1)$ for if it had some than A would have a point in W . We also know that $\mathbb{R^N}_{uniform}$ is completely separable, and there is a continuous function f that separates 0 and X−B(0,1) $ \subseteq $ W′. So, f is continous in the finer box topology as well, and separates 0 from h(A).
This way we show that 0 can be separated by a continuous function from a closed set A that does not contain it.

Any comment woud be appreciated.

Thanks in advance.

答: If $\langle X_i:i\in I\rangle$ is any $I$-indexed family of regular spaces, then the box product $Y=\prod_{i\in I}X_i$ is regular. To see this, let $y=\langle x_i:i\in I\rangle \in Y$, with $C\subseteq Y\setminus\{y\}$ a closed set.  Then it is easy to check that, for each $i\in I$, there is a closed $C_i\subseteq X_i$ with $C\subseteq \prod_{i\in I}C_i\subseteq Y\setminus\{y\}$.  For each index $i$, we know that $x_i\not\in C_i$; so, using regularity of $X_i$, let $U_i,V_i$ be disjint open sets in $X_i$ such that $x_i\in U_i$ and $C_i\subseteq V_i$.  Then the sets $U=\prod_{i\in I}U_i$ and $V=\prod_{i\in I}V_i$ are open in the box topology, they're disjoint, $y\in U$, and $C\subseteq V$.  Thus $Y$ is regular.


问:
Example of a group which is abelian and has finite (except the $e$) and infinite order elements.

Exercise 7: Show that the elements of finite order in an abelian
  group $G$ form a subgroup of $G$

I just solved this exercise but I can't find example of a group which is abelian and has finite (except the $e$) and infinite order elements. Are there any well known such groups?

For not abelian group with other properties group of matrixes I know.

答: What about the group $\mathbb{Z}_2\times\mathbb{Z}$ ? $(1,0)$ has finite order and $(1,1)$ has infinite order.</p>


问:
Prove the Handshake Theorem by induction

Let $n \in \mathbb{N}$, and assume $n \geq 1$. Suppose you are at a party of $n$ people (including yourself). At the end of the party, define a person's parity as odd if they have shaken hands with an odd number of people, and even if they have shaken hands with an even number of people. Prove that the number of people of odd parity must be even.

My approach is first we find the base case, which is when $n = 1$, then there are $0$ people have shaken hands with an odd number of people, and $0$ is even, we are done.

For the induction step, we assume that for $k \in \mathbb{N}$ number of people, the number of people of odd parity must be even, we want to show for $k+1$ number of people, the number of people of odd parity is even as well. I tried to split it into two cases:

Case 1: The new person's parity is even

Case 2: The new person's parity is odd

But then I'm kind of stuck and don't know what to do since there are so many cases that can be and I wonder if there's a smarter approach.

答:
Without induction:

For each person, consider the number of handshakes they participated in. If you add these $n$ numbers, you should get two times the number of total handshakes that occurred (since each handshake is counted twice). Since the sum of these $n$ numbers is an even number, what does that say about the number of odd numbers?


答: Equivalently, parities have an even sum. The base step $n=0$ is trivial. Assume $n=k$ works, then add person $k+1$. If they shake hands with $j$ of the first $k$ people, the sum of parities increases modulo $2$ by $j+j=2j=0$.

Title: Prove the Handshake Theorem by induction

Body:
Let $n \in \mathbb{N}$, and assume $n \geq 1$. Suppose you are at a party of $n$ people (including yourself). At the end of the party, define a person's parity as odd if they have shaken hands with an odd number of people, and even if they have shaken hands with an even number of people. Prove that the number of people of odd parity must be even.

My approach is first we find the base case, which is when $n = 1$, then there are $0$ people have shaken hands with an odd number of people, and $0$ is even, we are done.

For the induction step, we assume that for $k \in \mathbb{N}$ number of people, the number of people of odd parity must be even, we want to show for $k+1$ number of people, the number of people of odd parity is even as well. I tried to split it into two cases:

Case 1: The new person's parity is even

Case 2: The new person's parity is odd

But then I'm kind of stuck and don't know what to do since there are so many cases that can be and I wonder if there's a smarter approach.


问:
How can letters abcdef can be arranged so that a appears before b, c appears before d and e appears before f?
How can letters abcdef can be arranged so that a appears before b, c appears before d and e appears before f? If a general formula can be derived with this?

Note: a may be somewhere before b or c may be somewhere before d or e may be somewhere before f.....it need not to be immediate but will include cases where they are immediate before

答:
Consider row with 6 blocks...now two blocks to put (a,b) can be put using $\binom{6}{2}$....c and d can now be put in remaining 4 places using ${4 \choose 2}$. Total ways ${6 \choose 2}* {4 \choose 2}$ =90 ways

A general formula can be derived as ${n \choose 2}* {n-2 \choose 2}*{n-4 \choose 2}* {n-6 \choose 2}*{n-8 \choose 2}* {n-8 \choose 2}......$


答:
For notational convenience, I'll write

$$x_{t+1}=ax_t+(1-a)t.$$

The non-homogeneous equation has the obvious solution

$$x_t=ca^t.$$

Then we try the ansatz

$$x_t=pt+q,$$ which gives

$$p(t+1)+q=a(pt+q)+(1-a)t$$ and by identification

$$x_t=t+\frac1{a-1}.$$

Hence the general solution

$$x_t=t+\frac1{a-1}+ca^t.$$

Title: Solving a non-homogenous recurrence relation

Body:
I am trying to solve the following non-homogeneous recurrence relation i.e. trying to find $x_t$:

$$x_{t+1}=\left(1-\frac{1}{n}\right)x_t+\frac{t}{n}$$

My attempt: By writing the first few terms of the sequence $\{x_t\}_{t\geq 1}$, we see that

$$x_4=\left(1-\frac{1}{n}\right)^4x_0+\frac{1}{n}\left(1-\frac{1}{n}\right)^2+\frac{2}{n}\left(1-\frac{1}{n}\right)+\frac{3}{n}$$

and hence:

$$x_t=\left(1-\frac{1}{n}\right)^tx_0 + \sum_{k=1}^{t-2}\frac{k}{n}\left(1-\frac{1}{n}\right)^{t-1-k}+\frac{t-1}{n}$$

So I am having trouble finding the second term $\sum_{k=1}^{t-2}\frac{k}{n}\left(1-\frac{1}{n}\right)^{t-1-k}$. Any ideas?


答:
Focus on only one pair at a time. In total $N!$ permutations, the sequences $AB$ and $BA$ occur equal number of times. Then $AB$ occurs $N!/2$ times.

If there are $n$ pairs of symbols relevant, we're looking for the following formula:

$$\frac{N!}{2^n}$$

For instance, here $N=6,n=3$. Answer is $$\frac{6!}{2^3}=90$$

Body:
How can letters abcdef can be arranged so that a appears before b, c appears before d and e appears before f? If a general formula can be derived with this?

Note: a may be somewhere before b or c may be somewhere before d or e may be somewhere before f.....it need not to be immediate but will include cases where they are immediate before


答:
The number of participants in a handshake is two.

For any number $n$ handshakes. If we sum the number of times each person has participated in a handshake we will count 2n participations.

Supposing an odd number of people participated in an odd number of handshakes.  The total count of participations will be an odd number.  This contradicts our earlier statement.

If you want a proof by induction.

Base case $n=1$
One person shakes hands with nobody and there are 0 people with an odd number of handshakes.

Suppose for all gatherings of $n$ people our proposition holds.

When the n+1th guest arrives, he has experienced 0 handshakes and our proposition continues to hold.  For each handshake that occurs after this guest's arrival, it changes the parity of both participants.  Number of people who have experienced an odd number of handshakes changes by $0, 2,$ or $-2.$

If our proposition holds for $n$ people it must hold for $n+1$ people.


问:
$A \times \left(B \times C\right) \cong \left(A \times B\right) \times C$
I am proving the associativity of set products:

Suppose $A$, $B$ and $C$ are linearly ordered sets. Then
\begin{equation*}
A \times \left(B \times C\right) \cong \left(A \times B\right) \times C,
\end{equation*}
where the order of products is anti-lexicographic.

Proof. Define a function $f: A \times \left(B \times C\right) \to \left(A \times B\right) \times C$ such that
\begin{equation*}
\forall a \in A, \forall b \in B, \forall c \in C, f\left(a,\left(b,c\right)\right) = \left(\left(a,b\right),c\right).
\end{equation*}
It is obvious that $f$ is bijective. Next we shall prove the following statement:
\begin{equation*}
\left(a_{1},\left(b_{1},c_{1}\right)\right) <_{A \times \left(B \times C\right)} \left(a_{2},\left(b_{2},c_{2}\right)\right) \Longleftrightarrow \left(\left(a_{1},b_{1}\right),c_{1}\right) <_{\left(A \times B\right)\times C} \left(\left(a_{2},b_{2}\right),c_{2}\right).
\end{equation*}
Naturally, assume $\left(a_{1},\left(b_{1},c_{1}\right)\right) <_{A \times \left(B \times C\right)} \left(a_{2},\left(b_{2},c_{2}\right)\right)$. This condition can be decomposed into the following categories:

$c_{1} <_{C} c_{2}$

$c_{1} = c_{2}$ and $b_{1} <_{B} b_{2}$

$c_{1} = c_{2}$ and $b_{1} = b_{2}$ and $a_{1} <_{A} a_{2}$

If $c_{1} <_{C} c_{2}$, then it is clear that $\left(\left(a_{1},b_{1}\right),c_{1}\right) <_{\left(A \times B\right)\times C} \left(\left(a_{2},b_{2}\right),c_{2}\right)$. Next, if $c_{1} = c_{2}$ and $b_{1} <_{B} b_{2}$, then it is also clear that $\left(\left(a_{1},b_{1}\right),c_{1}\right) <_{\left(A \times B\right)\times C} \left(\left(a_{2},b_{2}\right),c_{2}\right)$. Finally, if $c_{1} = c_{2}$ and $b_{1} = b_{2}$ and $a_{1} <_{A} a_{2}$, we also have $\left(\left(a_{1},b_{1}\right),c_{1}\right) <_{\left(A \times B\right)\times C} \left(\left(a_{2},b_{2}\right),c_{2}\right)$.

Next, assume that $f\left(a_{1},\left(b_{1},c_{1}\right)\right) <_{\left(A\times B\right)\times C} f\left(a_{2},\left(b_{2},c_{2}\right)\right)$, that is,
\begin{equation*}
\left(\left(a_{1},b_{1}\right),c_{1}\right) <_{\left(A \times B\right)\times C} \left(\left(a_{2},b_{2}\right),c_{2}\right).
\end{equation*}
Then, we have the following categories:

$c_{1} <_{C} c_{2}$

$c_{1} = c_{2}$ and $b_{1} <_{B} b_{2}$

$c_{1} = c_{2}$ and $b_{1} = b_{2}$ and $a_{1} <_{A} a_{2}$

The argument is similar to our previous one. Thus, we may conclude that
\begin{equation*}
\left(a_{1},\left(b_{1},c_{1}\right)\right) <_{A \times \left(B \times C\right)} \left(a_{2},\left(b_{2},c_{2}\right)\right) \Longleftrightarrow \left(\left(a_{1},b_{1}\right),c_{1}\right) <_{\left(A \times B\right)\times C} \left(\left(a_{2},b_{2}\right),c_{2}\right).
\end{equation*}
As a result, we have
\begin{equation*}
A \times \left(B \times C\right) \cong \left(A \times B\right) \times C.
\end{equation*}

I am learning elementary set theory on my own. Is it a solid proof?

答:
You’re really done once you show that

$$\langle\langle a_1,b_1\rangle,c_1\rangle<_{(A\times B)\times C}\langle\langle a_2,b_2\rangle,c_2\rangle\tag{1}$$

and

$$\langle a_1,\langle b_1,c_1\rangle\rangle<_{A\times(B\times C)}\langle a_2,\langle b_2,c_2\rangle\rangle\tag{2}$$

are both equivalent to the assertion that either

$c_1<_C c_2$, or

$c_1=c_2$ and $b_1<_Bb_2$, or

$c_1=c_2$, $b_1=b_2$, and $a_1<_Aa_2$.

You could, however, stand to say a bit more to justify these equivalences. For $(1)$ it’s pretty clear, but for $(2)$ I’d say more than you did:

$(2)$ means that either $\langle b_1,c_1\rangle<_{B\times C}\langle b_2,c_2\rangle$, or $\langle b_1,c_1\rangle=\langle b_2,c_2\rangle$ and $a_1<_Aa_2$. This in turn means that either $c_1<_Cc_2$, or $c_1=c_2$ and $b_1<_Bb_2$, or $c_1=c_2$, $b_1=b_2$, and $a_1<_Aa_2$.


问:
Can someone explain "cascaded" evaluation of inequalities of log probabilities?
I am working with Markov Chain Monte Carlo (MCMC) methods and I have come across several examples of "cascaded evaluation" of log probabilities.

For example, suppose you have a rejection criterion of the form:

$$r > p_1p_2p_3$$

where $r$ is a random number drawn from the uniform distribution $U(0,1)$, and $p_1$, $p_2$, $p_3$ are independent probabilities with values between 0 and 1.

In log probability, the inequality can be written as:

$$\mathrm{log}(r) > \mathrm{log}(p_1)+\mathrm{log}(p_2)+\mathrm{log}(p_3)\tag{1}$$

In order to save compute time, I have seen that some people evaluate the inequality by doing a "cascaded evaluation":

Draw $r_1$ as a single random number from the uniform distribution

If $\mathrm{log}(r_1) > \mathrm{log}(p_1)$, then reject

Else Draw $r_2$ as a single random number from the uniform distribution

If $\mathrm{log}(r_2) > \mathrm{log}(p_2)$, then reject

-Else Draw $r_3$ as a single random number from the uniform distribution

-If $\mathrm{log}(r_3) > \mathrm{log}(p_3)$, then reject

This saves time because if you reject on the first if statement, you can avoid all the additional inequalities. However, I don't understand how this method satisfies the original inequality in $(1)$. Drawing multiple random numbers and evaluating each part of the summation separately doesn't seem to make sense because the full summation could still hold even if you reject all the individual parts.

Am I missing something obvious here? Or is there something special about the properties of log probabilities and/or uniform distributions and/or inequalities?

Any info is appreciated.

答:
If the goal is to accept with probability $p_1 p_2 p_3$ then it suffices to do three independent checks that would result in acceptance with probability $p_i$, and accept only if all three checks passed (since then the probability that all three checks passed is $p_1 p_2 p_3$ as desired).

One way to describe this mathematically is to say that if $X_i$ are independent Bernoulli($p_i$) variables then $\prod_{i=1}^n X_i$ is a Bernoulli($\prod_{i=1}^n p_i$) variable. Then as soon as any $X_i$ is known to be zero, the product $\prod_{i=1}^n X_i$ can be short-circuit evaluated without needing to know the other $X_i$.


问:
Total probabilities of being admitted to any university
Let's provide an hypothetical situation in which a student applies to 10 different universities whose number of applicants, admissions and admission rate you can see in the table below.

```
------------------------------------------------------
| Name      | Applicants | Admitted | Admission rate |
------------------------------------------------------
| Columbia  |  329281    |  22885   |     6.95%      |
| Stanford  |  280915    |  19945   |     7.10%      |
| MIT       |  111963    |  10894   |     9.73%      |
| CalTech   |   17471    |   2231   |    12.77%      |
| Cornell   |  117590    |  21131   |    17.97%      |
| Berkeley  |  167324    |  36142   |    21.60%      |
| UCLA      |  159635    |  40675   |    25.48%      |
| Virginia  |   73030    |  24297   |    33.27%      |
| Rochester |   30261    |  10319   |    34.10%      |
| UCSD      |   80544    |  28593   |    35.50%      |
------------------------------------------------------
```

How can we estimate the total probabilities of being admitted in any of these 10 universities? We also have to take in account that some of the other applicants may have also applied to more than one university.

I'd be grateful if you could redirect me to any similar question or provide me any useful formula to solve this problem. Thanks for your interest.

Source: USNews Education

答:
This is generally easier to solve by the completary situation, that is: What's the probability of NOT being accepted by any universtiy? Then the one you're looking for will be $1-x$. Now that's easier to calculate because you just have to use the product rule: probabilities of each of them multiplied, as it's only one way of not being accepted anywhere, which is all universities rejecting you, that is:

$$P(NO)=\Pi_i(1-p_i)$$
Being $p_i$ the admission rate/100. The result is 0.092, which is a 9.2%, so the probability of being admited in some university is 100-9.2=90.74%.


问:
How to solve an equation with variable exponents?
I have an equation of the form

$$x^a+(1-x)^b = 1$$

where $a$ and $b$ are constants.

Is there some way to manipulate this equation to solve for $x$?

Below is some more information about the problem for some context, although I don't think it affects the mathematics from the above equation.

I am looking at mixing relations for the electrical resistivity in porous media. Usually, we use something called Archie's Law:

$$\rho_b = \rho_f \phi ^{-m}$$

where $\rho_b$ is the bulk resistivity, $\rho_f$ is the fluid resistivity, $\phi$ is the porosity, and $m>0$ is a cementation exponent. In my case, the porosity, $\phi$, is unknown. For the above equation, it is easy to manipulate to solve for $\phi$. However, this simplistic equation is not sufficient for all problems and there is an alternative known as Modified Archie's Law which takes the form:

$$\rho_b\rho_m\phi^m + \rho_b\rho_f(1-\phi)^p = \rho_f\rho_m$$

This form incorporates the surrounding rock resistivity (i.e. the matrix resistivity, $\rho_m$) and uses an additional exponent, $p$. Now, if I want to solve for $\phi$, it is not clear how I can manipulate the equation.

Any help is appreciated.

答:
No, there is no general solution.

Because when $a,b$ are integer the equation is polynomial and it is well known that analytical solutions do not always exist.


问:
Mathematics Article Collection Books for Talented High School Students
I'm looking for some good books including mathematics articles which are appropriate for talented high school students. I'm NOT looking for puzzle or Olympiad problem books. Here are some of my findings, which may serve as examples:

Strange Curves, Counting Rabbits, & Other Mathematical Explorations.

How to Guard an Art Gallery and Other Discrete Mathematical
Adventures.

Kvant Selecta: Combinatorics.

Kvant Selecta: Algebra and Analysis, 1.

Kvant Selecta: Algebra and Analysis, 2.

Do you have any other suggestion?

Thanks.

答:
There is a rather large list available here.

I would add to it (for really strong students)

V. Prasolov, Y. Solovyev Elliptic Functions and Elliptic Integrals.

This book is devoted to the geometry and arithmetic of elliptic curves and to elliptic functions with applications to algebra and number theory. It includes modern interpretations of some famous classical algebraic theorems such as Abel's theorem on the lemniscate and Hermite's solution of the fifth degree equation by means of theta functions. Suitable as a text, the book is self-contained and assumes as prerequisites only the standard one-year courses of algebra and analysis.


问:
Gibbs’ Lemma in Thermodynamics
Ignoring all physical constants, I wish to show that the Maxwell-Boltzmann distribution $e^{-|v|^2}dv$ minimizes the entropy functional $\int_{\mathbb{R}^3} f\log f\,dv$ among all probability distribution with the same mass, momentum, and energy, i.e. the 0'th, 1st and 2nd moments are fixed. This is what I have: since for any $\varphi\in C^\infty_c(\mathbb{R}^3)$ with vanishing 0,1,2 order moments, we have $0=\frac{d}{d\epsilon}\bigg|_{\epsilon = 0}\int (f+\epsilon\varphi)\log(f+\epsilon\varphi)dv = \int\varphi(\log f +1)dv$. How do I now get the Euler-lagrange equation for $f$? This sounds like a job for lagrange multipliers but it's not clear to me how to implement it.

答:
I'm not sure if this is what you're looking for, but here is how to impose the Lagrange multipliers. We wish to maximize

$$
S=-\int dv \ f(v) \ln f(v)
$$

I'm using $dv=dv_x dv_ydv_z$, and $v=\vec{v}$. Implementing the constraints as Lagrange multipliers $\lambda$ we have

$$
S=-\int dv \ f(v) \ln f(v) + \lambda_0 \left( \int dv \ f(v)-m_0 \right) + \lambda_{1,j} \left( \int dv \ v_j f(v)-m_{1,j} \right)+ \lambda_2 \left( \int dv \ v^2f(v)-m_2 \right)
$$

The $m_n$ are the nth moments the you have specified. We must have $m_0=1$. I've had to label the velocity components with $j$ since this isn't the speed distribution. I think the Maxwell distribution is defined as entropy maximum with fixed energy only, so we shouldn't really have the constraint $\lambda_1$. Leaving it in for now, take the derivative w.r.t. $f$

$$
\partial_fS=-\int dv \ \ln f(v) - \int dv \ +\lambda_0 \int dv + \lambda_{1,j}\int dv \ v_j+\lambda_2\int dv \ v^2=0 \\
\partial_fS=-\int dv \ \left( \ln f +1-\lambda_0-\lambda_{1,j}v_j-\lambda_2v^2\right)=0
$$

Setting the integrand equal to $0$, and solving for $f$

$$
f(v)=\exp(-1+\lambda_0+\lambda_{1,j}v_j+\lambda_2v^2)=A \exp(\lambda_{1,j}v_j+\lambda_2v^2)
$$

I've introduced the constant $A$ for simplicity. Now one solves for the $\lambda$ (and $A$) by imposing the constraints:

$$
1=\int dv \ A \exp(\lambda_{1,j}v_j+\lambda_2v^2) \\
m_{1,k} =\int dv \ v_k A \exp(\lambda_{1,j}v_j+\lambda_2v^2) \\
m_2 = \int dv \ v^2 A \exp(\lambda_{1,j}v_j+\lambda_2v^2)
$$

In principle, you do the integrals, get simultaneous equations for the $\lambda$, and solve for them. Here, I think symmetry alone dictates that $\lambda_{1,j}=0$ and thus $m_{1,k}=0$. Assuming this is so, we have

$$
1=\int dv \ A \exp(\lambda_2v^2) \\
m_2 = \int dv \ v^2 A \exp(\lambda_2v^2)
$$

The first integral is a product of Gaussians. The second may be evaluated in spherical $v$ co-ordinates. In any case, that there are solutions for $A$ and $\lambda_2$ justifies the functional form you seek. I find

$$
A=\left( \frac{3}{2 \pi m_2} \right)^{3/2} \\
\lambda_2 = -\frac{3}{2m_2}
$$

Title: Gibbs’ Lemma in Thermodynamics


问:
Show that $2^n<2^{\lceil n \log_23\rceil}-3^n<3^n-2^n$
Is there a way to show that (with integer $n>2$) $$2^{\lceil n \log_23\rceil}-3^n<3^n-2^n$$
I tried to figure a way with derivative or by looking how both side are growing, but I have some trouble with the ceiling function.

答:
Start by showing that
$$2^{\lceil \log_23^n\rceil}=2^{\lceil n \log_23\rceil}<3^n$$
Then the rest follows!


答:
When a new person is added, that person shakes hands with $p$ people and that alter the previous parity.

Assuming the statement true for some k:

There are $k_1$ even people

There are $k_2$ odd people and $k_2$ mod $2$ = $0$

Adding a new person who shake hands with $p$ people (case $k+1$)

If he shakes hands with $p_1$ even people, that people become odd

If he shakes hands with $p_2$ odd people, that people become even

$p_1$ + $p_2$ = $p$

The new number of odd people are:

Case1: $k_2$ - $p_2$ + $p_1$ + 1 if $p$ is odd

Case2: $k_2$ - $p_2$ + $p_1$ if $p$ is even

By induction hypothesis, $k_2$ is even.

And because $p_1$ - $p_2$ = $p$ - $2p_2$ we can conclude that $p_1$ - $p_2$ = $p$ mod $2$

In both cases, the number of odd people is even.


问:
Cross section of a plane in a cube
A plane is going through a cube so the cross section is a pentagon. Prove that the area of the pentagon is smaller than the product of the pentagon's two largest sides.

The first thing I tried to do was to express some of the sides through pythagorean theorem, however i failed to do so as not all sides are a part of a right triangle. I don't have any idea after this.

答:
Sharing an approach that you can turn into a more formal proof -

The point to observe is that if the cross section of the cube cut by the plane is a pentagon, it must go through $5$ sides of the cube and two pairs of sides must be  parallel (that are on parallel sides of the cube). Here is a visualization -

In the diagram, we have $AB \parallel ED, AE \parallel BC$ and
$AB \gt DE$ and $AE \gt BC$.

If we extend line $ED$ and line $BC$ and say they meet at point $M$ then we have a parallelogram $ABME$.

WLOG, $AB$ is the longer side and $AE$ is the smaller side of the parallelogram $ABME$.

Area of pentagon $ \lt$ area of parallelogram ABME $ \leq \ AB \cdot AE \leq P, $ where $P$ is the product of the two largest sides of the pentagon.

So the inequality clearly hold even if $DE \gt AE \ $ or $CD \gt AE$ or $AB$.

Title: Cross section of a plane in a cube


问:
Does eigenvalues of matrix change after multiplication by unitary matrix?
For a matrix $A \in \mathbb{C}^{n \times n}$, does multiplication by a unitary matrix $U$ change the eigenvalues of $A$? So for:

$$Ax = \lambda x \qquad \mathrm{and} \qquad AUy = \mu y $$

does $\lambda = \mu$ for some $x,y \in \mathbb{C}^n$?

I know the above is true for doing left and right multiplication by $U$:

$$ UAU^*y = \mu y \\
AU^*y = \mu U^* y \\
Az = \mu z \\
\therefore \mu = \lambda$$

(defining $z = U^* y$)

Under the guise that unitary matrices are simply rotations, it logically makes sense to me that $\mu$ and $\lambda$ should be identical, and only the the eigenvectors should be different. The statement is true for singular values (see here), but I'm having trouble proving it for eigenvalues (if it even is true).

Edit

After a quick example in python, I understand that the above is not true. So instead: where is my thought process going wrong with regard to how unitary matrices/rotations effect eigenvalues?

Edit 2

What I was really going for, but did not state correctly was that:

$$AX = \Lambda X \qquad \mathrm{and} \qquad AUY = MY \\$$

such that $ \lambda \in M, \forall \lambda \in \Lambda$, where $M$ and $\Lambda$ are diagonal matrices.

答:
Your intuition is somewhat correct, but you are doing it wrong. When you mean a rotation, to what does it apply? To vectors, right?

So, if $A$ is the matrix of a linear map , we expect that if we rotates the axes, the the matrix changes, but the application is still the same, so the eigenvalues should be the same. Let's check this.

Let $f$ be a linear map from an $n$-dimensional vector space $E$ into itself, and $\mathcal B$ a basis of $E$. Let $A$ the matrix of $f$ in that basis. And let another basis $\mathcal B'$, with a matrix $P$ of change of basis, which is regular. That is, if $v$ is a vector in $E$ with coordinates $X\in\Bbb R^n$ in the basis $\mathcal B$, then the coordinates $X'$ in the basis $\mathcal B'$ satisfy (note the order):

$$X=PX'$$

Now, in the new basis, $f$ has another matrix representation $A'$, that is given by

$$A'=P^{-1}AP$$

How does it impact eigenvectors and eigenvalues? Let $u$ an eigenvector of $A$ for the eigenvalue $\lambda$, then $Au=\lambda u$ and, since $A=PA'P^{-1}$

$$PA'P^{-1}u=\lambda u$$

Hence

$$A'P^{-1}u=P^{-1}\lambda u=\lambda P^{-1}u$$

That is, $\lambda$ is also an eigenvalue of $A$, for the eigenvector $u'=P^{-1}u$. Which we can write $u=Pu'$. For the eigenvector $u'$, we simply apply the change of basis: it's the same vector in $E$, only its representation in a basis changes.

That is, the eigenvectors and eigenvalues of a linear map don't depend on the basis.

Note that for this we don't require $P$ to be unitary.


问:
Prove that the data given produce the fibonnaci sequence if that is indeed the solution
I am looking into the following puzzle:

Male bees hatch from unfertilized eggs and so have a mother but no
father.   Female bees hatch from fertilized eggs. How many ancestors
does a male have in the $12th$ generation back? How many of these are
males?

So I realized that the numbers are following the Fibonacci sequence but noticing the pattern is not a proof (as the question asks for a specific link with the given data).

My attempt of a proof is the following:

Conjecture: the ancestry follows the Fibonnaci series and hence in the $12th$ generation there are $233$ ancestors and $89$   of them are males.

Proof:

Each male bee contributes $1$ (female) ancestor in the ancestry chain while each female bee contributes to $2$ ancestors (male and female).

This means that at each level of the ancestry tree we have by the definition of the problem statement:

$mb_i=fb_{i-1}$

$fb_i=fb_{i-1} + mb_{i-1} = fb_{i-1} + fm_{i -2}$

where $mb$ denotes the number of male bees and $fb$ the number of female bees

The $fb$ number follows the fibonnaci sequence and the $mb$ is the fibonacci number created at the previous level of the ancestry.

The total number of ancestors at generation $i$ is $mb_i + fb_i$ which is a summation of two fibonnaci sequences where one starts at $0$ and the other at $1$. Therefore this leads to the conclusion that the total number is also following the fibonnacci sequence.

I feel that there is a gap in the last $3$ statements of the proof. Is there is something that is omitted but is required  in order to consider that we have proven that the total number follows the Fibonnaci?

Is this a correct proof based on the actual structure of the data and not just on observing the numbers produced?

答:
The presentation can be improved, but you have all of the essential elements. I’m going to change your notation, however: I’ll use $f_n$ for the $n$-th Fibonacci number, with $f_0=0$ and $f_1=1$, $m_n$ for the number of male bees $n$ generations back, with $m_0=1$, and $q_n$ for the number of female bees $n$ generations back, with $q_0=0$. As you say

$$m_n=q_{n-1}\tag{1}$$

and

$$q_n=q_{n-1}+m_{n-1}=q_{n-1}+q_{n-2}\,.$$

Moreover, $q_0=0$, and $q_1=q_0+m_0=0+1=1$. This means that the sequence $\langle q_n:n\in\Bbb N\rangle$ follows the same recurrence as the Fibonacci sequence and has the same two initial values, so it must be the same sequence: $q_n=f_n$ for all $n\in\Bbb N$. In particular, $q_{12}=f_{12}=144$. It then follows immediately from $(1)$ that $m_n=f_{n-1}$ for each $n\in\Bbb N$, so $m_{12}=f_{11}=89$.

Finally, as you saw, the total number of ancestors $n$ generations back is

$$q_n+m_n=q_n+q_{n-1}=q_{n+1}=f_{n+1}\,,$$

and in particular the total number of ancestors $12$ generations back is $f_{13}=233$.


答:
If you calculate $n \cdot \log_2 (3)$ for $n = 1, 2, 3, ...$ and look at the digits after the decimal point, you will get a rather unpredictable looking sequence of numbers from 0 to 1. Using the ceil function will increase the argument by an amount between 0 and 1, so two raised to this power will be somewhere between $3^n$ and $2 \cdot 3^n$.

Your inequality will be wrong if $n \cdot\log_2(3)$ is just a tiny bit larger than an exact integer. You can calculate how close it has to be to make the inequality wrong. You can calculate how likely it would be, if those last digits were random. Since these digits are not random, but in fact predictable, it could be possible to prove this either way. Others have commented that it seems to be an unsolved problem.

$2^n$ gets small compared to $3^n$ very quickly, so I’d be willing to make a small bet that the inequality is indeed true, but would be absolutely unable to prove it.

Title: Show that $2^n<2^{\lceil n \log_23\rceil}-3^n<3^n-2^n$

Body:
Is there a way to show that (with integer $n>2$) $$2^{\lceil n \log_23\rceil}-3^n<3^n-2^n$$
I tried to figure a way with derivative or by looking how both side are growing, but I have some trouble with the ceiling function.


问:
Mapping from a perspective projected square to the original one
A square viewed from an angle becomes an isosceles trapezoid. Assuming we are looking at the middle of the square, if we know everything about this trapezoid, how to map every coordinate on it to the original square?

The intersection of the trapezoid's diagonals is the midpoint of the square. From there, we can calculate the width (and thus height) of the square, by finding the width of the trapezoid at the y coordinate of the midpoint.

It seems to me that this allows us to find the corresponding x coordinate on the square for any point on the trapezoid by linearly interpolating the width.

A more complicated matter, and the subject of this question is finding the y coordinate on the square. For simplicity, let us assume that the top of the trapezoid is at y = 0, and the bottom is at y = 1. Same for the square.

Obviously the top of the trapezoid maps to the top of the square, and the bottom to the bottom. So 0 maps to 0, and 1 maps to 1. Again using the midpoint of the square which we located on the trapezoid by its diagonals, we can find that 1/(p+1) maps to 0.5, where p is the ratio between the bottom and top base lengths.

Visually, it is evident that we can continue finding the midpoints between any two found points, effectively allowing us to find any point, and showing that the mapping I seek exists, but aside from a complicated recursive definition, I can't find a formula for it. Any ideas?

答:
TL;DR: See $\eqref{G4}$ below, under "There is a single solution, yielding".

Without loss of generality, we can pick a 3D coordinate system where the eye is at origin $(0, 0, 0)$, we look along the positive $z$ axis, $x$ axis being right, $y$ axis up, and the projective plane is at $z = 1$; and we have a rectangle with vertices at $(-x_r, y_0, z_0)$, $(x_r, y_0, z_0)$, $(x_r, y_1, z_1)$, and $(-x_r, y_1, z_1)$.  Perspective projection to the projective plane at $z = 1$ is
$$\left\lbrace \, \begin{aligned}
\chi = x^\prime &= \frac{x}{z} \\
\gamma = y^\prime &= \frac{y}{z} \\
z^\prime &= \frac{z}{z} = 1 \\
\end{aligned} \right.$$
Note, this is not an approximation, this is exact with the above conditions.

The projected coordinates for the four vertices are
$$\left\lbrace \, \begin{aligned}
\chi_{00} &= -\frac{x_r}{z_0} \\
\gamma_{00} &= \frac{y_0}{z_0} \\
\end{aligned} \right., \quad \left\lbrace \, \begin{aligned}
\chi_{01} &= \frac{x_r}{z_0} \\
\gamma_{01} &= \frac{y_0}{z_0} \\
\end{aligned} \right., \quad \left\lbrace \, \begin{aligned}
\chi_{10} &= -\frac{x_r}{z_1} \\
\gamma_{10} &= \frac{y_1}{z_1} \\
\end{aligned} \right., \quad \left\lbrace \, \begin{aligned}
\chi_{11} &= \frac{x_r}{z_1} \\
\gamma_{11} &= \frac{y_1}{z_1} \\
\end{aligned} \right.$$

We can parametrise the surface of the rectangle with $0 \le u \le 1$, $0 \le v \le 1$ using
$$\left\lbrace \, \begin{aligned}
x &= x_r (2 u - 1) \\
y &= y_0 + (y_1 - y_0) v \\
z &= z_0 + (z_1 - z_0) v \\
\end{aligned} \right.$$
The projected coordinates for the parametrised surface are
$$\left\lbrace \, \begin{aligned}
\chi &= \frac{ x_r (2 u - 1) }{ z_0 + (z_1 - z_0) v } \\
\gamma &= \frac{ y_0 + (y_1 - y_0) u }{ z_0 + (z_1 - z_0) v } \\
\end{aligned} \right. \tag{1}\label{G1}$$
and its inverse is
$$\left\lbrace \, \begin{aligned}
u &= \frac{ \chi (y_0 z_1 - y_1 z_0) + \gamma x_r (z_1 - z_0) - x_r*(y_1 - y_0) }{ 2 \bigl ( \gamma x_r (z_1 - z_0) + x_r (y_0 - y_1) \bigr) } \\
v &= \frac{y_0 - \gamma z_0 }{ \gamma (z_1 - z_0) - (y_1 - y_0) } \\
\end{aligned} \right. \tag{2}\label{G2}$$
The last equation is the one we need, except that we also need a way to derive the constants $x_r$, $y_0$, $z_0$, $y_1$, and $z_1$ from the projected coordinates $\chi_{00}$ through $\gamma_{11}$.

However, now that we have the form of $u(\chi, \gamma)$ and $v(\chi, \gamma)$ functions, we can instead use that form with simple constants, and fit those constants to the observed coordinates!

(This is a trick I personally use often with Computer Algebra Systems like wxMaxima, because it is much less work than finding how to map the known constants to $\eqref{G2}$.  As long as we don't accidentally omit any coefficients, this works perfectly.  So, do compare $\eqref{G2}$ and $\eqref{G3}$ to see they have the same form.)

For simplicity, I will use $x$ (instead of $\chi$) for the projected $x$ coordinate, and $y$ (instead of $\gamma$) for the projected $y$ coordinate, since we no longer care about the actual 3D coordinates. We have
$$\left\lbrace \, \begin{aligned}
u(x, y) &= \frac{U_0 + U_1 x + U_2 y}{y + U_3} \\
v(x, y) &= \frac{V_0 + V_1 y}{y + V_2} \\
\end{aligned} \right. \tag{3}\label{G3}$$
Let's say the four vertices of the isosceles trapezoid are at $(-x_1, y_1)$, $(+x_1, y_1)$, $(+x_2, y_2)$, and $(-x_2, y_2)$.  The diagonals cross at $(0, y_0)$, where
$$y_0 = \frac{x_1 y_2 + x_2 y_1}{x_1 + x_2}$$
Now we have seven equations for seven unknowns to solve:
$$\left\lbrace \, \begin{aligned}
u(-x_1, y_1) &= 0 \\
u(+x_1, y_1) &= 1 \\
u(-x_1, y_2) &= 0 \\
u(+x_1, y_2) &= 1 \\
\end{aligned} \right. \quad \text{ and } \quad \left\lbrace \, \begin{aligned}
v(0, y_1) &= 0 \\
v(0, y_0) &= \frac{1}{2} \\
v(0, y_2) &= 1 \\
\end{aligned} \right.$$
There is a single solution, yielding
$$\left\lbrace \, \begin{aligned}
u(x, y) &= \frac{ x (y_2 - y_1) + y (x_2 - x_1) + x_1 y_2 - x_2 y_1 }{2 \bigl( y (x_2 - x_1) + x_1 y_2 - x_2 y_1 \bigr) } \\
v(x,y) &= \frac{ (y - y_1) x_2 }{ y (x_2 - x_1) + x_1 y_2 - x_2 y_1 } \\
\end{aligned} \right. \tag{4}\label{G4}$$
Note that this is not an approximation; this is correct for any rectangle whose projected corners are at $(-x_1, y_1)$, $(+x_1, y_1)$, $(+x_2, y_2)$, and $(-x_2, y_2)$.

Also note that $u(-x_1, y_1) = u(-x_2, y_2) = 0$, $u(0, y) = 1/2$, $u(x_1, y_1) = u(x_2, y_2) = 1$, $v(x, y_1) = 0$, $v(x, y_2) = 1$, and $v(x, y_0) = 1/2$ where $y_0$ is the $y$ coordinate where the diagonals of the projected trapezoid intersect, $y_0 = (x_1 y_2 + x_2 y_1) / (x_1 + x_2)$.


问:
Product rule or chain rule?
Does one take the product rule or chain rule when there are 3 terms with variable being multiplied together.

example

taking
$$ x = r\cdot \cos \theta \cdot \sin \phi $$

at an instant in time

$$ x(t) = R(t) \cdot \cos\theta(t) \cdot \sin\phi(t)  $$

to derive in order to obtain

$$ \dot{x}=R'(t) \cdot \cos'\theta(t) \cdot \sin'\phi(t) $$

I'm leaning towards product rule because

$$ f'(x)g(x)h(x) + f(x)g'(x)h(x) + f(x)g(x)h'(x) $$

but just doesn't seem to be coming out right.

I end up with

$$ \big(1 \cdot \cos\theta (t) \cdot \sin\phi (t)\big) + \big(R(t)\cdot (-\sin\theta (t) )\cdot \sin\phi (t)\big) + \big(R(t)\cos\theta (t) \cdot \cos\phi (t) \big) $$

答:
If I am understanding correctly that $$x(t) = r(t)\cos(\theta(t))\sin(\phi(t))$$ then you will need both the product and chain rules to differentiate with respect to $t$.  You will get
\begin{align*}
x'(t) &= r'(t)\cos(\theta(t))\sin(\phi(t)) - r(t)\sin(\theta(t))\theta'(t)\sin(\phi(t))\\[5pt] &\quad + r(t)\cos(\theta(t))\cos(\phi(t))\phi'(t).
\end{align*}

Title: Product rule or chain rule?


问:
Is learning (theoretical) physics useful/important for a mathematician?
I'm starting to read The Princeton Companion to Mathematics, at the beginning it says:

A proper appreciation of
  pure mathematics requires some knowledge of applied
  mathematics and theoretical physics.

Some of my professors have told me that modern Mathematics require some knowledge about Quantum Mechanics and theoretical Physics.

I attended the second and third day of the José Adem Memorial Lecture Series by Matilde Marcolli at the beginning of this year, they were about Number theory, Quantum statistical Mechanics and Quantum Field theory. I did not understand a single word but somehow the few things I understood had a big impression on me.

Please give me some examples of pure Mathematics that require/use Physics.

答:
A more simple example than the very good examples given above is: find the geometric shape with the minimal face area that is based upon the vertices of a cube. A mathematician would have to do a great deal of calculations, but a physicist would just drawn the cube in a bucket full of soap water.

P.S. In his book "The Music of the Primes" the author, Marcus du Sautoy, tells us about how the Quantum Mechanics helped to predict and give new information about pure mathematic research. It is a book easy to read and I enjoyed it a lot.


问:
Probability $k$ bins are non-empty
The following problem arises in the analysis of Bloom filters.

Consider $m$ bins and $N=nk$ balls placed uniformly and independently at random into the bins. A query chooses $k$ bins uniformly and independently at random and asks if they are all non-empty.  The main question is as follows.

What is the probability that all $k$ bins in the query are non-empty?

It is assumed that this probability will be a function of $k$, $m$ and $n$.

The second question is:

For what value of $k$ (which is a function of $m$ and $n$) is this probability minimized?

The standard version of the analysis taught the world over and reproduced in the wikipedia page linked above contains a "now the magic occurs" step which ignores the non-independence of the bins. It gives $k \approx \frac{m}{n} \ln{2}$ as the answer to the second question.

Is there a clean and rigorous way of doing this analysis correctly?

This is a repost of this one which hasn't had any good answers yet.

Clarification.

The difficultly arises because the probability that all $k$ bins are non-empty is not $(1-(1-\frac{1}{m})^{kn})^k$. The reason is that the probability that one of the $k$ (not necessarily distinct) bins that is queried is non-empty is dependent on whether the other queries return non-empty bins.

An approximate answer or good bounds will suffice.

答: The probability that the bit is not set in the Bloom filter after $nk$ trials is equal to $(1-\frac 1 m)^{nk}\approx e^{-\frac{nk}{m}}$, if $k$ is big enough. The probability of $k$ filter collisions is equal to $(1-e^{-\frac{nk}{m}})^{k} = (1-e^{-\frac{n}{m}k})^{k}=f(k,m,n)$. This function has the minimum exactly in $\frac m n \ln(2)$, if the $\frac n m$ is fixed.</p>

Title: Probability $k$ bins are non-empty


问:
Confused about subset example

Theorem: Let $f: X \to Y$ be a function. Then, for all subsets $A, B$ of $X, \  f(A \cap B) \subseteq f(A) \cap f(B)$.

...

What if $f$ is not one-one? The above observation gives you a hint to produce an example where the inclusion is proper. If $f$ is not one-one, there exist $x_1, x_2 \in X, x_1 \ne x_2$ such that $f(x_1) = f(x_2) = y \in Y$. Choose $A = \{x_1\}, B = \{x_2\}$. Then, $A \cap B = \emptyset$, and so $\color{red}{f(A \cap B) = \emptyset \not \subseteq \{y\} = f(A) \cap f(B)}$.

My question is about the $\color{red}{\text{part in red}}$ above. I think it's incorrect for two reasons: (1) it contradicts the theorem above and (2) $\emptyset \subseteq \{y\}.$ Is it possible that the authors meant to conclude $f(A) \cap f(B) = \{y\} \not \subseteq \emptyset = f(A \cap B)$? Just making sure I follow my book.

Snapshot from my book

答: The example they gave is standard and it is not wrong, rather your notation is off. What they mean is that when $f$ is not injective, then it is not always true that $f(A \cap B) = f(A) \cap f(B)$ for all subsets $A, B \subseteq X$ (they prove one inclusion, while the other is not hard to prove exactly the way the authors were proposing in the case that $f$ is actually injective).

Title: Confused about subset example


答:
I think it means that $f(A \cap B) = \emptyset \subset \{y\} $ but the sets are different
(an example where the inclusion is proper).

Title: Confused about subset example

Body:
Theorem: Let $f: X \to Y$ be a function. Then, for all subsets $A, B$ of $X, \  f(A \cap B) \subseteq f(A) \cap f(B)$.

...

What if $f$ is not one-one? The above observation gives you a hint to produce an example where the inclusion is proper. If $f$ is not one-one, there exist $x_1, x_2 \in X, x_1 \ne x_2$ such that $f(x_1) = f(x_2) = y \in Y$. Choose $A = \{x_1\}, B = \{x_2\}$. Then, $A \cap B = \emptyset$, and so $\color{red}{f(A \cap B) = \emptyset \not \subseteq \{y\} = f(A) \cap f(B)}$.

My question is about the $\color{red}{\text{part in red}}$ above. I think it's incorrect for two reasons: (1) it contradicts the theorem above and (2) $\emptyset \subseteq \{y\}.$ Is it possible that the authors meant to conclude $f(A) \cap f(B) = \{y\} \not \subseteq \emptyset = f(A \cap B)$? Just making sure I follow my book.

Snapshot from my book


问:
Equivalent versions of the Mayer-Vietoris axiom in Brown theorem
In the hypotheses of Brown representability theorem
there is a contravariant functor F from pointed connected CW complexes to pointed sets, which must respect two axioms, the second of which is the so-called “Mayer Vietoris” axiom. There are apparently three different versions of this axiom, which I presume are all equivalent, but why?

First version F sends homotopy pushouts to weak pullbacks

Second version $F(A \cup B) \to F(A)_{xF(A \cap B)} F(B)$ (where $F(A)_{xF(A \cap B)} F(B)$ is the homotopy fibre product of $F(A)$ and $F(B)$) is surjective.

Third version For any CW-triad $(X, A_1, A_2)$ and for any $x_1 \in F(A_1)$, $x_2 \in F(A_2)$, $(x_1)|_{A_1 \cap A_2} = (x_2)|_{A_1 \cap A_2}$, there is $y \in F(X)$ with $y|_{A_1} = x_1$ and $y|_{A_2} = x_2$

答:
There's evidently a relation between the three conditions, considering that

a CW-triad is a triple of spaces $(X,A_1,A_2)$ such that $X = A_1\cup A_2$, and

a weak pullback is "a pullback with just existence, not uniqueness" -a condition that translates into a certain comparison map being surjective-.

You also need a small set of other pieces, like for example the relationship between cofibrations and homotopy pushouts (an homotopy pushout of a cospan, where one leg is a cofibration, is computed as a regular pushout). Now, the square
$$
\begin{array}{ccc}
A\cap B &\to & A \\
\downarrow && \downarrow \\
B &\to& A\cup B
\end{array}
$$ is a pushout (and a pullback, for that matter), and the inclusions of $A\cap B$ in $A,B$ are cofibrations (am I right? Just 99% sure), so the above remark applies.

In slightly more modern terms, the axioms for which Brown representability holds are these two:

(the categorical terminology in this pictureis proper of $\infty$-categories, but for the sake of the discussion here what matters is only that this allows you to remove the prefix "homotopy-" from all pushouts; plus, this is a particularly sleek statement of BRT; the part I removed is just a boilerplate assumption that the category of CW complexes satisfies, and that here one must impose on $\mathcal C$).

So, let's take $(b)$ above as the "standard" MV property; if $(b)$ is true, now, using my observation 3. you get condition 2 of your list. Now, a little bit of yoga (to be precise, first Virabhadrasana) unwinding the definition of pullback translates the second into the third condition of your list.


问:
Prove that all diagonal entries of a negative definite matrix are negative
We know that all principal minors of order one are nonpositive, but is there a way to prove that all of them are negative? I looked at a similar question here but the solution is too vague, so if possible, please explain it in more detail.</p>

答:
If you choose the vector $x=(0,0,\dots,1,\dots)$ with the $1$ in the $k$-th position, then
$$
x^TAx=a_{kk}
$$
Since $x\neq 0$ you should have $a_{kk}<0$.


问:
Prove the Handshake Theorem by induction

Let $n \in \mathbb{N}$, and assume $n \geq 1$. Suppose you are at a party of $n$ people (including yourself). At the end of the party, define a person's parity as odd if they have shaken hands with an odd number of people, and even if they have shaken hands with an even number of people. Prove that the number of people of odd parity must be even.

My approach is first we find the base case, which is when $n = 1$, then there are $0$ people have shaken hands with an odd number of people, and $0$ is even, we are done.

For the induction step, we assume that for $k \in \mathbb{N}$ number of people, the number of people of odd parity must be even, we want to show for $k+1$ number of people, the number of people of odd parity is even as well. I tried to split it into two cases:

Case 1: The new person's parity is even

Case 2: The new person's parity is odd

But then I'm kind of stuck and don't know what to do since there are so many cases that can be and I wonder if there's a smarter approach.

答:
I think your approach is good, and you are almost there.

... the base case, which is when $n = 1$, then there are $0$ people have shaken hands with an odd number of people, and $0$ is even, we are done.

For the induction step, we assume that for $k \in \mathbb{N}$ number of people, the number of people of odd parity must be even, we want to show for $k+1$ number of people, the number of people of odd parity is even as well.

Consider a party of $k$ people with $a$ people having even handshake parity and $b$ people having odd parity. By the induction hypothesis, $b$ is even. Then a new person is added and due to their handshakes, $c$ existing guests are changed even to odd and $d$ from odd to even.

Case 1: The new person's parity ($c{+}d$) is even. The new number of odd-parity people is $b{+}c{-}d$. Note that since $c{+}d$ is even, $c{+}d-2d=c{-}d$ is also even. Thus $b{+}c{-}d$ is even as required.

Case 2: The new person's parity is odd. The new number of odd-parity people is $b{+}c{-}d{+}1$ (the $+1$ for the new person). Now $c{+}d$ is odd, $c{+}d{+}1$ is even and $c{+}d{+}1-2d=c{-}d{+}1$ is also even. Thus the odd parity count $b{+}c{-}d{+}1$ is again even as required.


问:
Spivak Ch. 3 Question 4
From Spivak Calculus 4th Edition, Chapter 3, Question 4:

Let $S(x) = x^2$, let $P(x) = 2^x$ and let $s(x) = \sin x$. Find each of the following. In each case your answer should be a number.

(i)   $(S \circ P)(y)$

(ii)  $(S \circ s)(y)$

(iii) $(S \circ P \circ s)(t) + (s \circ P)(t)$

(iv)  $s(t^3)$

The part I am struggling with is "your answer should be a number." How can the answer be a number if we are composing functions that are not inverses of each other?

答:
In the four parts, we are going to use that if $f$ and $g$ are any two functions, we define a new function $f\circ g$ by
$$(f\circ g)(x)=f(g(x)).$$

(i) We have that
$$(S\circ P)(y)=S(P(y))=S(2^y)=(2^y)^2=\boxed{2^{2y}}$$
(ii) We have that
$$(S\circ s)(y)=S(s(y))=S(\sin y)=(\sin y)^2=\boxed{\sin^2 y}$$
(iii) We have that
\begin{align*}
        (S\circ P\circ s)(t)+(s\circ P)(t) &= (S\circ P)(s(t))+s(P(t)) =\\
        &= S[P(s(t)]+s(P(t)) =\\
        &= S[P(\sin t)]+s(2^t) =\\
        &= S(2^{\sin t})+\sin (2^t) =\\
        &= (2^{\sin t})^2+\sin (2^t) =\\
        &= \boxed{2^{2\sin t}+\sin (2^t)}
    \end{align*}
(iv) We have that
$$s(t^3)=\boxed{\sin (t^3)}$$

Let us now make clear the meaning that the answer has to be a number: in the different sections, we have that $y,t\in \mathbb{R}$ are any real number, therefore, the result as it only depends on $y$ or $t$, it is also a real number.

Title: Spivak Ch. 3 Question 4


问:
Proof that $\;\dfrac{x}{1+x^2}\;$ is a bounded function.
I don't quite understand how $\dfrac1 x$ is unbounded while $\dfrac{x}{1+x^2}$ is not.

答:
We have
$$\quad\lim\limits_{x \to 0}\space (x)=0
\qquad \text{while}\qquad
\lim\limits_{x \to 0}\space (x^n+1)=1\quad$$
so the limit is as follows

$$
\lim\limits_{x \to 0}\frac{1}{x}=\infty\qquad
\text{while}\qquad
\lim\limits_{x \to 0}\bigg(\frac{x}{x^2+1}\bigg)
=\left(\frac{\lim\limits_{x \to 0}\space (x)}
       {\lim\limits_{x \to 0}\space (x^n+1)}\right)
=\frac{0}{1}=0$$


问:
Inverse trignometry finding the interval for $x$

Derive the conditions on $x$ for which the equation holds:$$2\tan^{-1}x=\sin^{-1}\frac{2x}{1+x^2}$$

How to find value of $x$ for which the equation holds?

答:
Given
$$2\tan^{-1}x = \sin^{-1}\frac{2x}{1+x^2}$$

Let $2\theta = 2\tan^{-1}x$

From the RHS,
$$x = \tan\theta$$
and
$$\tan2\theta = \frac{2x}{1-x^2}$$

From the LHS,
$$\sin2\theta = \frac{2x}{1+x^2}$$
so
$$\cos2\theta = \pm \frac{1-x^2}{1+x^2}$$
since
$$(1+x^2)^2 = (1-x^2)^2 + (2x)^2$$
hence
$$\tan2\theta = \pm\frac{2x}{1-x^2}$$

The signs of the LHS & RHS must agree, so $\cos2\theta \ge 0$. Hence $2\theta$ is in the 1st or 4th quadrants, i.e.,
$$-\frac\pi2 \le 2\theta \le \frac\pi2$$
$$-\frac\pi4 \le \theta \le \frac\pi4$$
$$\tan\frac{-\pi}4 \le \tan\theta \le \tan\frac\pi4$$
$$-1 \le x \le 1$$


问:
Solving $e^{-x} + x e^{-x} + \frac12x^2e^{-x} + \frac16x^3 e^{-x}=0.99$
Equation:

$$e^{-x} + x e^{-x} + \frac12 x^2 e^{-x} + \frac16x^3e^{-x}=0.99$$

I tried simplifying it and got it down to

$$e^{-x}\left(6+6x+3x^2+x^3\right)=5.94$$

although I am not sure how I would solve the $(6+6x+3x^2+x^3)$ portion.

Thanks to Wolfram Alpha I know the roots (solution for $x$), so I am really looking for guidance on how you would approach this equation and how far you can simplify it before having to use a calculator.

答:
1.)

$$e^{-x} + x e^{-x} + \frac12 x^2 e^{-x} + \frac16x^3e^{-x}=0.99\ \ \ |\cdot 6$$

$$e^{-x}\left(6+6x+3x^2+x^3\right)=5.94\ \ \ |\cdot 100e^x$$

$$600+600x+300x^2+100x^3=594\ e^x\ \ \ |-594e^x$$

$$600+600x+300x^2+100x^3-594e^x=0$$

Because your equation is an irreducible algebraic equation of $x$ and $e^x$, it cannot be solved by an $x\neq 0$ by elementary functions or elementary numbers. That's a consequence of the theorems in [Ritt 1925]/[Risch 1979], [Lin 1983], [Chow 1999].

Your equation cannot be solved using Lambert W either.

The usual computer algebra systems cannot solve this equation in closed form either. A generalized Lambert W like in Alex R.'s answer is needed.

[Chow 1999] Chow, T.: What is a closed-form number. Am. Math. Monthly 106 (1999) (5) 440-448

[Lin 1983] Ferng-Ching Lin: Schanuel's Conjecture Implies Ritt's Conjectures. Chin. J. Math. 11 (1983) (1) 41-50

[Risch 1979] Risch, R. H.: Algebraic Properties of the Elementary Functions of Analysis. Amer. J. Math. 101 (1979) (4) 743-759

[Ritt 1925] Ritt, J. F.: Elementary functions and their inverses. Trans. Amer. Math. Soc. 27 (1925) (1) 68-90

2.)

You could split your unwieldy equation into a system of two equations. Take your equation

$$e^{-x}\left(6+6x+3x^2+x^3\right)=5.94.$$

Substitute $5.94=ce^{-x}$, where $c\in\mathbb{C}$.

$$e^{-x}\left(6+6x+3x^2+x^3\right)=ce^{-x}$$

$$6+6x+3x^2+x^3=c$$

That's an algebraic equation in $x$. It's of degree $3$ and you could solve it e.g. in closed form first.


问:
Universal introduction with a limited vocabulary
I understand (I think) how to apply Universal Introduction in general, but am uncertain how to use it with a specified limited vocabulary.

For example, given a language with a finite set of object constants, $\{a,b,c\}$ from the premises

$$\Pi =\{p(a),p(b),p(c)\}$$

I can use Universal Introduction to conclude things like

$$\Pi \vdash\forall x.p(a)$$

or

$$\Pi \vdash\forall c.p(c)$$

but I don't see how I can use these premises to get

$$\Pi \vdash\forall x.p(x)$$

even though it is clearly the case (I think) that

$$\Pi \models\forall x.p(x)$$

Can I use using (finite) Herbrand semantics to get this result?

答:
$\Pi \not\vDash \forall x. p(x)$, and hence $\Pi \not\vdash \forall x. p(x)$. The problem is that you could have objects in your domain which aren't named. Here's a model which satisfies $\Pi$, but doesn't satisfy $\forall x. p(x)$: Let the domain consist of 5 objects, and let 4 of those objects be $p$-objects (i.e. put 4 objects into the extension of $p$). Give the names $a,b,c$ to 3 of those $p$-objects. This will satisfy $\Pi$ but fail to satisfy $\forall x. p(x)$, since we have one lonely non-$p$ object in the domain, i.e. the extension of $p$ is not the entire domain.

Now, if you included in $\Pi$ the extra sentence $\forall x (x = a \vee x = b \vee x = c)$, then we would have $\Pi \vDash \forall x. p(x)$, since this extra sentence guarantees that all of the objects are named by one of the three constants. To show $\Pi + \forall x (x = a \vee x = b \vee x = c) \vdash \forall x. p(x)$, you could use identity rules from your deduction system.

If you're using (finite) Herbrand semantics, then your deduction system should have some sort of "domain closure rule" which allows you to deduce $\forall x.p(x)$ given every instance of $p(x)$, which in this case is $\Pi$. See this webpage from Stanford for more details.


问:
Are these Jacobian and Hessian forms correct?
Reference is made to a book appendix

From my understanding, $\mathbf{F}=[f_1,\ldots,f_m]^T$ is a column vector function of $\mathbf{x}$ on $\mathbb{R}^n$, then

Where in the last equation, $\nabla\mathbf{F}(\nabla\mathbf{F})^T$ is a matrix but $\sum_if_i\nabla^2f_i$ is a column vector?
But if applied with vector identity, the expected is $$\nabla\cdot[(\nabla\mathbf{F})\mathbf{F}]=(\nabla^2\mathbf{F})\mathbf{F}+\nabla\mathbf{F}\cdot\nabla\mathbf{F}.$$

Which is the correct one or where is the pitfall I came into?

答:
We have
$F(x)=\begin{pmatrix}f_1\\...\\f_m\end{pmatrix}$ and $\nabla F=\begin{pmatrix}\frac d {dx_1}f_1&...&\frac d {dx_1}f_m\\...\\\frac d {dx_n}f_1&...&\frac d {dx_n}f_m\end{pmatrix}$

So

$$\nabla F(x)F(x)=\begin{pmatrix}\sum_{i=1}^m f_i\frac d {dx_1}f_i\\...\\\sum_{i=1}^m f_i\frac d {dx_n}f_i\end{pmatrix}$$

The part of the chain rule that corresponds to the second part is

$$\nabla F(x)F(x)=\begin{pmatrix}\sum_{i=1}^m f_i\underbrace{\frac d {dx_1}f_i}\\...\\\sum_{i=1}^m f_i\underbrace{\frac d {dx_n}f_i}\end{pmatrix}$$

Apply the chain rule to get

$$\nabla\left(\nabla F(x)\right)F(x)=\begin{pmatrix}\sum_{i=1}^m f_i\frac {d^2} {dx_1^2}f_i&...&\sum_{i=1}^m f_i\frac {d^2} {dx_1dx_n}f_i\\...\\\sum_{i=1}^m f_i\frac {d^2} {dx_ndx_1}f_i&...&\sum_{i=1}^m f_i\frac {d^2} {dx_n^2}f_i\end{pmatrix}$$

Does this match the book appendix's $\sum_{i=1}^m f_i(x)\nabla ^2 f_i(x)$?

See $\nabla f_i(x)=\begin{pmatrix}\frac d {dx_1}f_i(x)\\...\\\frac d {dx_n}f_i(x)\end{pmatrix}$ and $\nabla^2 f_i(x)=\begin{pmatrix}\frac {d^2} {dx_1}f_i(x)&...&\frac {d^2} {dx_1dx_n}f_i(x)\\...\\\frac {d^2} {dx_ndx_1}f_i(x)&...&\frac {d^2} {dx_n^2}f_i(x)\end{pmatrix}$

so after you multiply $\nabla^2 f_i(x)$ by $f_i(x)$ and take the sum, yes, it is correct: $\nabla\left(\nabla F(x)\right)F(x)=\sum_{i=1}^m f_i(x)\nabla ^2 f_i(x)$


问:
Solving The Differential Equation $\frac{dy}{dt} = \frac{at+by+m}{ct+dy+n}$ where $ad=bc$.
I have solved the differential equation $\frac{dy}{dt} = \frac{at+by+m}{ct+dy+n}$ where each of the alphabets $a,b,c,d,m,$ and $n$ is some constant and $ad=bc$ by the following method.

Multiplying the RHS of the differential equation by $\frac{d}{d}$, one obtains

$\frac{dy}{dt} = \frac{adt+bdy+md}{cdt+d^{2}y+nd}$

Because $ad = bc$, the equation is re-expressed as

$\frac{dy}{dt} = \frac{b(ct+dy)+md}{d(ct+dy)+nd}$

Let $x = ct + dy$

One obtains $\frac{dy}{dt} = \left( \frac{1}{d} \right)\left(\frac{dx}{dt} -c\right)$

The differential equation is re-expressed as

$\frac{dx}{dt} = \frac{(b+c)x+(md+cn)}{x+n}$

Rearranging the above equation, one obtains

$\left(\frac{x+n}{(b+c)x+(md+cn)}\right)\frac{dx}{dt} = 1$

Multiplying the LHS of the above equation by $\frac{\left(\frac{1}{b+c}\right)}{\left(\frac{1}{b+c}\right)}$, one obtains

$\left(\frac{1}{b+c}\right)\left(\frac{x+n}{x+\left(\frac{md+cn}{b+c}\right)}\right)\frac{dx}{dt} = 1$

Let $h$ denotes $\left(\frac{md+cn}{b+c}\right)$

$\left(\frac{1}{b+c}\right)\left(\frac{x+n}{x+h}\right)\frac{dx}{dt} = 1$

Integrating both sides of the above differential equation with respect to $t$,

$\left(\frac{1}{b+c}\right)\int \left(\frac{x+n}{x+h}\right)\frac{dx}{dt} dt = \int dt$

One obtains,

$x + (n-h)$ln$|x+h| + K = (b+c)t$

where $K$ is an arbitrary constant.

Substituting $x$ as $ct + dy$ and $h$ as $\left(\frac{md+cn}{b+c}\right)$,

$(ct + dy) + (n-\left(\frac{md+cn}{b+c}\right))$ln$|(ct + dy)+\left(\frac{md+cn}{b+c}\right)| + K = (b+c)t$

The above equation is my solution to the differential equation.

However, when applying the solution to the differential equation

$\frac{dy}{dt} = \frac{-t -2y -3}{2t+4y-1}$

each of the terms with $\left(\frac{md+cn}{b+c}\right)$ is undefined.

Is the reason for the case is because my solution to the differential equation is incorrect?

The differential equations are obtained from the book Differential Equations and Their Applications: An Introduction to Applied Mathematics, 4th Edition by Martin Braun on the section 1.4.

答:
It is obvious that the problem here is that $b+c=0$. To proceed, you implicitly made the assumption where you divide by $b+c$ that $b+c\neq 0$, so any step after that assumption doesn't apply when setting it equal to zero. However, before that step the analysis is sound and in fact you can indeed set it to be zero at the step where you derived

$$\frac{dx}{dt}=\frac{(b+c)x+(md+cn)}{x+n}$$

which you can solve (it is separable)

$$\int\frac{x+n}{md+cn}dx=\int dt\iff\frac{x^2+2nx}{2(md+cn)}=t+C~,~C\in \mathbb{R} $$


问:
What alternatives are there to the generalized continuum hypothesis?
Since the generalized continuum hypothesis is independent of ZFC, we can adopt its negation as an axiom. However, this would not be a very "nice" axiom, since all it does is assert that there is at least one instance in which GCH fails.

My question is what axioms have been studied that prove the negation of the GCH, but has many more consequences than the negation of GCH. In particular, I am looking for ones that mathematicians would consider appealing axioms for mathematical foundations, not merely any statement that implies the negation of the GCH.

As an example, I would consider the Axiom of determinacy a "nice" alternative to the Axiom of choice.

答:
I'm personally a fan of the inner model hypothesis - or rather, hypotheses might be more appropriate. IMHs should be understood as codifications of the general idea that "Anything which can happen, does" in a precise sense via inner and outer model theory.

Specifically, the idea is that the set-theoretic universe $V$ should be maximally rich with respect to inner models. For example, both $\mathsf{CH}$ and $\neg\mathsf{CH}$ are "easy to achieve" via forcing, so $V$ should have inner models where $\mathsf{CH}$ holds and inner models where $\mathsf{CH}$ fails. A bit more specifically:

Anything which can happen in an inner model of an outer model of $V$, already happens in some inner model of $V$.

I personally find this idea quite attractive. The technicality of inner/outer models is definitely something which can give someone new to the field pause, but I think is actually very natural - especially in light of the role that forcing and inner model constructions already play in set theory.

Of course this is all wildly imprecise, and this is where the pluralization above comes in: there are multiple different ways one might try to formulate this principle. See here (and the papers cited therein) for more details on this point. The point is that even a mild IMH makes the continuum quite large. It also, interestingly, contradicts even the existence of a single inaccessible cardinal!


问:
Why n$\times$n identity matrix is the only matrix that is orthonormal, symmetric, and PD?
Here is my thoughts, but I am not sure whether they are correct...

Since A is symmetric, then A = A^T. Also we know it is square and orthonormal, A^T * A = I.
Therefore with these two facts, we know A^2 = I.

Then I can get two possible solution: A = I or A = -I. Since for a PD matrix, all eigenvalues should be positive, therefore A cannot be -I, the only solution is A = I

Appreciate any helps!

答:
$A^2=I$ does not imply $A=\pm I$.  It implies that $A=A^{-1}$ and many matrices do that.  For example, the real matrices
$$A=\begin{pmatrix} 1 & t \\ 0 & -1\end{pmatrix}$$
for any $t \in \mathbb{R}$ satisfy $A^2=I$.  (h/t:  Ben Grossman)


问:
Is there a name for this property/theorem of divisibility in modular arithmetic?
Statement: Given $S = az \pm b$ and $T = ak \pm b$, and $a \neq b$:

$$S \mid T \iff k \equiv \pm z \pmod S$$

This holds true only if the three instances of $\pm$ multiply to $+$, i.e., all are $+$ or exactly two are $-$. (Proof at the end.)

I assume I have not discovered something even vaguely new; in fact, this seems like it ought to be a somewhat basic theorem or property, but in going through some online texts and discussions, I don't see it anywhere. It's possible that it's related to the CRT, since we have

$$S \equiv \pm b \pmod a \\
T \equiv \pm b \pmod a \\
k \equiv \pm z \pmod S$$

But since $S$ and $T$ are different integers in the same residue class and the same moduls, but their divisibility is related to the... I guess here, $z$ and $k$ are the quotients by Eucliden division(?)... this doesn't seem to fit with the normal applications of the CRT.

Does anyone know of a name for this theorem or property, or have a reference to it/about it?

Proof: Take all of the instances of $\pm$ to be positive. We have:

$$S = az + b \\
T = ak + b$$

And the claim is that $S \mid T \iff k \equiv +z \pmod S$. Taking this equivalence between $k$ and $z$, we can rewrite $k$ as:

$$k = nS + z = n(az+b) + z$$

for some integer $n$. Then

$$T = ak+b = a(n(az+b)+z)+b  \tag{1}$$
$$T = a^2nz+anb+az+b = an(az+b) + (az+b) = (az+b)(an+1) \tag{2}$$

The RHS of $(1)$ contains all three of the signs of interest. Replacing any two with negative signs gives the equivalents:

$$T = a(n(az-b)-z)+b = (az-b)(an-1)\\
T = a(n(az-b)+z)-b = (az-b)(an+1)\\
T = a(n(az+b)-z)-b = (az+b)(an-1)$$

Taking all three or any one sign as negative leads to a mismatch, requiring $S$ to be both $az+b$ and $az-b$.

答:
$\!\bmod az-b\!:\ \color{#c00}{b\equiv az}\,$ so $\,ak-\color{#c00}b\equiv ak-\color{#c00}{az}\equiv a(k-z),\,$ so $\,ak-b\equiv 0\iff \color{#90f}a(\color{#0a0}{k-z})\equiv 0.\,$ This is not generally equivalent to $\,\color{#0a0}{k\equiv z}\,$ except when $\,\color{#90f}a\,$ is cancellable (= invertible), i.e. when $\,1 = (a,\,az-b) = (a,b).\,$ Then $\, b/a\equiv ba^{-1}$ is the unique root of $\,ax\equiv b,\,$ so since $\,k\,$ and $z$ are roots we deduce $\,k\equiv z\,$ by uniqueness.

There is no standard name for such simple inferences from basic congruence laws, but it can be interpreted as uniqueness of (multivalued) modular fractions, as explained briefly here (it shows that the reduced fraction is unique w.r.t. a reduced modulus, i.e. when we reduce the fraction by cancelling its gcd, we must also cancel the gcd from the modulus too, i.e. cancel it everywhere). But this is not a standard topic, since almost all ENT authors omit treatment of  modular fractions at such introductory levels.