问:
Cross product of three vectors and Levi-Civita Symbol
I know the basics of Levi Civita and I thought I didn’t have a problem when it comes to calculating the cross product of two vectors. But how and why can we just take the j component of a on the r.h.s of the equation that I share below? And why could we eliminate the basis vector and make it a scalar equation although it should yield a vector? Could you explain the logic behind it?

答:
Remember that
$\epsilon_{kij}\epsilon_{kmn} = \delta_{im}\delta_{jn} - \delta_{in}\delta_{jm}$

so that (I keep the basis vecotrs in the full expansion of the LC symbol)

$\vec a \times (\vec b \times \vec c) = \hat e_i \epsilon_{ijk} a_j (\epsilon_{kmn} b_m c_n )$

$ = \hat e_i ( \delta_{im}\delta_{jn} - \delta_{in}\delta_{jm} )a_j b_m c_n $

$ = \hat e_i \delta_{im}\delta_{jn} a_j b_m c_n -  \hat e_i \delta_{in}\delta_{jm} a_j b_m c_n$

$ = \hat e_i a_j b_i c_j - \hat e_i a_j b_j c_i $

You may want to double check these indices are in the correct spot.


问:
What is orthogonal projection of zero to triangle generated by three points (0,1) (5,0) and (2,4)

What is orthogonal projection of zero to triangle generated by three points (0,1) (5,0) and (2,4)

Well, in my opinion, there is none. However, my teacher think that it has but he don't know how to find it.

答:
Well, if you mean the unique (but not necessarily orthogonal) projection of a point $P$ to a closed convex set $C$ as the endpoint $Q$ of the shortest segment $PQ$ with $Q\in C$, then

in your example, if you draw it, it should be clear that the shortest path from the origin to the given triangle is indeed its orthogonal projection to the side with endpoints $(0,1),\,(5,0)$. This has direction vector $(5,0)-(0,1)=(5,-1)$, and its normalvector is (any parallel to) $(1,5)$.

So, the projection of the origin is on both lines
$$\begin{align}
y&=5x\\
x+5y&=5\,.
\end{align}$$
And you still have to calculate its distane from the origin.

ContentLicense: CC BY-SA 3.0


问:
Substituting $x = \sec(u)$ to evaluate $\int\sqrt{x^2-1}\ dx$: but why is $\tan(u) = \sqrt{x^2 - 1}$ rather than $\tan(u) = -\sqrt{x^2 - 1}\ $?

I tried evaluating $\int\sqrt{x^2-1}\ dx$ using the substitution $x = \sec(u).$

I know my method gets to the same answer as WolframAlpha, namely:

$$\int\sqrt{x^2-1}\ dx = \frac{1}{2} \left(\ x \sqrt{x^2-1} - \ln\left|x + \sqrt{x^2-1}\right|\ \right) + C,\quad (*)$$

but there is one step I can't justify. When I got to
$$\int \tan^2(u)\sec(u)\ du = \frac{1}{2}\left(\ \tan(u)\sec(u) - \ln\left|\sec(u)+\tan(u)\right|\ \right) + C,$$
I then have to substitute stuff back in terms of $x$. Now
$$x=\sec(u) \implies \tan^2(u) = x^2 - 1,$$
but I don't see how this implies $\tan(u) = \sqrt{x^2 - 1}$.

Comparing the graphs of $\sec(u)$ and $\tan(u)$, I don't see why not: $\ \tan(u) = -\sqrt{x^2 - 1}$, which would give:

$$\int\sqrt{x^2-1}\ dx = \frac{1}{2} \left(\ -x \sqrt{x^2-1} - \ln\left|x - \sqrt{x^2-1}\right|\ \right) + C,\quad (**)$$

which is a different answer than $(*)$ ?

Now I noticed that $(*) = -(**)\ $ (ignoring the $C \to -C)$.

I can see from the graph of $\sqrt{x^2-1}$ that for $x>1$, the definite integral $\int^x_1\sqrt{t^2-1}\ dt = (*),$ and for $x<-1,\ \int^{-1}_x\sqrt{t^2-1}\ dt = (**)$

So is the indefinite integral sort of poorly defined, or would you say it is:

$$\int\sqrt{x^2-1}\ dx = \pm \frac{1}{2} \left(\ x \sqrt{x^2-1} - \ln\left|x + \sqrt{x^2-1}\right|\ \right) + C?$$

答:
I tried evaluating $\int\sqrt{x^2-1}\ dx$ using the substitution $x = \sec(u).$

When I got to $$\int \tan^2(u)\sec(u)\ du = \frac{1}{2}\left(\ \tan(u)\sec(u) - \ln\left|\sec(u)+\tan(u)\right|\ \right) + C,$$

Correction (noting that $\sqrt{\tan^2(u)}=|\tan(u)|$ and that $|\tan(u)|\tan(u)=\operatorname{sgn}(\tan(u))\tan^2(u)$): $$\int\sqrt{x^2-1}\,\mathrm dx\\=\int \color{red}{\operatorname{sgn}(\tan(u))}\tan^2(u)\sec(u)\,\mathrm du \\= \frac{1}{2}\color{red}{\operatorname{sgn}(\tan(u))}\left(\tan(u)\sec(u) - \ln\left|\sec(u)+\tan(u)\right| \right) + C.$$

Now $$x=\sec(u) \implies \tan^2(u) = x^2 - 1,$$

So, $$\tan(u)=\color{red}{\operatorname{sgn}(\tan(u))}\sqrt{x^2-1}.$$

Then, by taking cases and noting, by rationalising denominator, that $$-\ln|x-\sqrt{x^2-1}|\equiv\ln|x+\sqrt{x^2-1}|,$$ this result is obtained:

I know my method gets to the same answer as WolframAlpha, namely: $$\int\sqrt{x^2-1}\ dx = \frac{1}{2} \left(\ x \sqrt{x^2-1} - \ln\left|x + \sqrt{x^2-1}\right|\ \right) + C\quad (*)$$

P.S. Technically, this indefinite integral requires two independent parameters rather than just the one $C$ above.

P.P.S. For definite integration, it will be important that your implicit substitution $x=\sec(u)$ be invertible, typically by restricting it to some choice of principal domain. Alternatively, Quanto's answer makes this explicit at the start of the above, more directly leading to the required answer.

P.P.P.S. If you are comfortable with hyperbolic functions, $x=\cosh(u)$ is a much more elegant and efficient substitution than $x=\sec(u).$

ContentLicense: CC BY-SA 4.0


问:
How do I solve a limit when direct substitution gives division by zero?
I have this limit.
$$\lim_{x\to 1}\frac{x^2+x+1}{x-1}$$
And direct substitution gives zero. What do I do? Thanks.

Body:
Limit does not exist in this case

$\lim_{x\to 1^+}\frac{x^2+x+1}{x-1}=\lim_{x\to 1^+}(x+2+\frac{3}{x-1})=\infty$

$\lim_{x\to 1^-}\frac{x^2+x+1}{x-1}=\lim_{x\to 1^-}(x+2+\frac{3}{x-1})=-\infty$


答:
In this case, the limit does not exist.

To get a feel for why this is:

If $x$  is a number very close to $1$, but  just a little bit bigger than $1$ (say $x =1 + 0.01$), what does that ratio look like?

On the other hand, if $x$  is a number very close to $1$, but  just a little bit smaller than $1$ (say $x =1 - 0.01 $), what does that ratio look like?

More explicitly, and even more 'rigorously' (sort of): if $x$ is a number very close to $1$, whether $x$ is a bit bigger or a bit smaller than $1$, the numerator $x^2+x+1$ is very close to $3$. Clearly. On the other hand, if $x$ is more than $1$ (but close to $1$), the denominator $x-1$ is very close to $0$ , but positive. So the ratio
$$ \text{approximately } 3\over \text{positive teensy} $$ is a large number.

On the other hand, if $x$ is close to, but smaller than $1$, the denominator $x-1$ is negative, so that the ratio
$$\text{approximately }3\over \text{negative teensy}$$
is a large negative number.

For a limit to exist (even if one allows 'infinity' as a value), there must be ONE value. Here we have two differing possibilities (plus a lot, and minus a lot). Hence there is no unique limit.

Hope this helps.

Title: How do I solve a limit when direct substitution gives division by zero?

Body:
I have this limit.
$$\lim_{x\to 1}\frac{x^2+x+1}{x-1}$$
And direct substitution gives zero. What do I do? Thanks.


问:
How to show two identical integrals $\; 2\int_{-r}^{r}f(x)dx=r\int_{-r}^{r}\sqrt{1+(df/dx)^{2}}dx$
With
$$ \;f(x)=(r^2-x^2)^{1/2}$$

show that$$\; 2\int_{-r}^{r}f(x)dx=r\int_{-r}^{r}\sqrt{1+(df/dx)^{2}}dx$$

by using integration by parts. Then, conclude that the area of a circle of radius r is $\;\pi r^2$ if we define $\;\pi=\;$ circumference$\;\div\;$ diameter

I thought the only method I can use is via trig substitutions. But, the problem asks to solve it with integration-by-parts.

I need help to solve this problem.
Thank you.

Body:
$$f(x)=(r^2-x^2)^{1/2}$$
$$f'(x)=-x(r^2-x^2)^{-1/2}$$
$$f'^2(x)=\frac{x^2}{r^2-x^2}$$
$$1+f'^2(x)=1+\frac{x^2}{r^2-x^2}=\frac{r^2-x^2+x^2}{r^2-x^2}=\frac{r^2}{r^2-x^2}$$
$$\sqrt{1+f'^2(x)}=r(r^2-x^2)^{-1/2}$$
so:
$$r\int_{-r}^r\sqrt{1+f'^2(x)}dx=r^2\int_{-r}^r(r^2-x^2)^{-1/2}dx$$
and:
$$2\int_{-r}^rf(x)dx=2\int_{-r}^r(r^2-x^2)^{1/2}$$
can u finish it from here?


问:
Gaussian elimination to solve half of vector values while the other values are varied
I am trying to solve a linear system using Gaussian elimination where a half of variables are varied and I need to solve the system to adapt the other half of variables in order to get the system correct.

For example, I have the the system $W*x = y$ where $W$ is known matrix and $y$ is known too, and half of the vector $x$ is varied, it mean it can by any random values,  what I need is to set the other half of the vector $d$ to get the correct equality of the system.

Example:

I have the system as following:

Suppose that the values of $x_1$ and $x_2$ are varied and can be any random values,  for example $1$ and $-1$, respectively. Therefore the above equation will be written as below:

I need to solve $k_1$ and $k_2$ to get the above equation right. Normally, as I know, we can do it as following:

Which gives:

Finally, that can be written as:

So, I cannot solve $k_1$ and $k_2$ in that case to solve the system in the first equation!!

My question, Is it possible to solve the variables $k_1$ and $k_2$ to make the equality right ?If not,  is there any other algorithm we can use it instead of Gaussian elimination to solve it?

Another example

$W = [0.5+0.5i , 0.5-0.5i; 0.5-0.5i, 0.5+0.5i]$,  and multiplied by a vector $[0.7; k]$; the resultant vector should be $y = [1; -1]$.   I think the value of $k$ which makes the multiplication correct should exist, is that right ? but how can we find it mathematically?

答:
$\def\m#1{ \left[\begin{array}{r}#1\end{array}\right] }$The full system is
$$Aw=b$$
Without doing any math, notice that the columns of $A$ are all orthogonal to one another (i.e. it has full rank), while $b$ is equal to the ${\tt2}^{nd}$ column and therefore the unique solution vector for the full system is the ${\tt2}^{nd}$ basis vector, i.e.
$$w = \m{0\\1\\0\\0}$$
Writing the system in partitioned form
$$
\big[V\quad W\big]\,\m{x\\k} = b
\qquad\implies\quad Wk = (b-Vx)
$$
does not change the solution. But choosing $x\ne\m{0\\1}$ makes the system inconsistent.

The best one can do in such circumstances is a least-squares solution
$$k = W^+(b-Vx) + (I-W^+W)y$$
where $W^+$ is the Moore-Penrose inverse and $y$ is an arbitrary vector.

For the given matrix $\quad W^+=\frac 14W^T$


问:
Simple way to apply distinct transformations to different parts of one vector?
I have a single vector
$\begin{pmatrix} a \\b \\ c \\ d \end{pmatrix} $, where I want to transform different elements using different matrices $X$ and $Y$. For example, I want to be able to evaluate the following expression:

$X\begin{pmatrix} a \\0 \\ 0 \\ d \end{pmatrix} +Y \begin{pmatrix} 0 \\b \\ c \\ 0 \end{pmatrix} $

Is there a simpler way to do this, perhaps with one well-designed matrix?

答:
Let $X_1,...,X_4$ be column vectors of $X$ in order and $Y_1,...,Y_4$ be column vectors of Y in order too. For standard basis vectors $e_1,e_2,e_3,e_4$

$v=c_1e_1+c_2e_2+c_3e_3+c_4e_4 \Rightarrow T(v)=c_1T(e_1)+c_2T(e_2)+c_3T(e_3)+c_4T(e_4)=A\begin{pmatrix} c_1 \\ c_2 \\ c_3 \\ c_4 \end{pmatrix}=Av$

$T(e_1)=X_1$

$T(e_2)=Y_2$

$T(e_3)=Y_3$

$T(e_4)=X_4$

so $A $ is a matrix whose i th column is $T(e_i)$


问:
Showing Logical Equivalence
Show that $(\lnot(p\lor(\lnot p\land q))$ is logically equivalent to $\lnot p \land \lnot q$.

I am wondering what I did is correct. Very new to learning simple logic.

$$(\lnot(p\lor(\lnot p\land q)) \equiv \lnot((p\lor\lnot p)\land(p\lor q)) \\ \equiv \lnot(\text{T} \land (p\lor q)) \\ \equiv\lnot(p \lor q) \\ \equiv \lnot p \land
\lnot q \\ \square$$

答:
This is an alternative rount, and corrects for your misuse of DeMorgan's in the last step.

$$(\lnot(p\lor(\lnot p\land q))) \equiv \lnot p \land \lnot(\lnot p \land q)\tag{DeMorgan's}$$
$$\equiv \lnot p \land (p \lor \lnot q)\tag{DeMorgan's}$$
$$\equiv (\lnot p \land p) \lor  (\lnot p \land \lnot q)\tag{Distributive Law}$$
$$\equiv F\lor (\lnot p \land \lnot q)$$
$$\equiv \lnot p \land \lnot q$$

Title: Showing Logical Equivalence


答:
The limit does not exist.

To prove it,
$\forall G>0$ we need to find $\delta$ s.t. $\forall x$ satisfy $|x-1|<\delta$ we have
$|\frac{x^2+x+1}{x-1}|>G$

Let $|x-1|<1$,
we have $1<(x+\frac{1}{2})^2+\frac{3}{4}<7$,

So,$|\frac{x^2+x+1}{x-1}|=|\frac{(x+\frac{1}{2})^2+\frac{3}{4}}{x-1}|>|\frac{1}{x-1}|$

Let $|\frac{1}{x-1}|>G$, we have $|x-1|<\frac{1}{G}$.

So,we take $\delta=\min(1,\frac{1}{G})$


问:
Proof by induction - algorithm
I need some help to sort out if my answer is right for this question. The algorithm calculates $x^n$.

Question: Argue the correctness of the algorithm using proof by induction.

Note: Even if you haven't managed to complete the previous proof, assume that expIterative(x, n) has been proven to be correct for any x ∈ R and n >= 0. Furthermore, remember that integer divison always rounds off toward 0, and consider the two cases when n is odd and when n is even. A proof by induction is most appropriate for this algorithm.

```<code>double expRecursive(double x, int n) {
    if (n <= 4) {
        return expIterativ(x, n);
    }

    return expRecursive(x, n/2) *
           expRecursive(x, (n + 1)/2);
}
</code>```

My answer:

Base Case:

We can from the note assume that it works for $n = 4$.

Inductive case:

Assume that is works for n = k: $expRecursive(x, \frac{k}{2}) \times expRecursive(x, \frac{k+1}{2}) = x^k$

Than show that it also works for $n = k + 1$:

FOR ODD N:

$expRecursive(x, \frac{k+1}{2}) \times expRecursive(x, \frac{k+2}{2}) = expRecursive(x, \frac{k+1}{2}) \times expRecursive(x, \frac{k+1}{2}) = x^{\frac{k+1}{2}} \times x^{\frac{k+1}{2}} = x^{k+1}$

FOR EVEN N:

$expRecursive(x, \frac{k+1}{2}) \times expRecursive(x, \frac{k+2}{2}) = expRecursive(x, \frac{k}{2}) \times expRecursive(x, \frac{k+2}{2}) = x^{\frac{k}{2}} \times x^{\frac{k+2}{2}} = x^{k+1}$

Is this the correct way to do it or how should I do it?

答:
The proof is correct.  The if-else statement

```<code>if (n <= 4) {
    return expIterativ(x, n);
}
</code>```

corresponds to the base case.

The induction hypothesis has been correctly stated.

The inductive step

```<code>return expRecursive(x, n/2)
       expRecursive(x, (n + 1)/2);
</code>```

is based on dividing $n=k+1$ into two cases according to its parity.  The logic in your proof is good.

Remarks: It's likely that you've omitted a * in your code.

```<code>return expRecursive(x, n/2) * expRecursive(x, (n + 1)/2);
</code>```

Title: Proof by induction - algorithm

Body:
The proof is correct.  The if-else statement

if (n <= 4) {
    return expIterativ(x, n);
}

corresponds to the base case.

The induction hypothesis has been correctly stated.

The inductive step

return expRecursive(x, n/2)
       expRecursive(x, (n + 1)/2);

is based on dividing $n=k+1$ into two cases according to its parity.  The logic in your proof is good.

Remarks: It's likely that you've omitted a * in your code.

return expRecursive(x, n/2) * expRecursive(x, (n + 1)/2);


答:
Only your last step is wrong:
$$\neg(p \lor q) \equiv (\neg p \land \neg q)$$

Title: Showing Logical Equivalence

Body:
Show that $(\lnot(p\lor(\lnot p\land q))$ is logically equivalent to $\lnot p \land \lnot q$.

I am wondering what I did is correct. Very new to learning simple logic.

$$(\lnot(p\lor(\lnot p\land q)) \equiv \lnot((p\lor\lnot p)\land(p\lor q)) \\ \equiv \lnot(\text{T} \land (p\lor q)) \\ \equiv\lnot(p \lor q) \\ \equiv \lnot p \land
\lnot q \\ \square$$


问:
Quick Circle Cross Sections Question
So I was given the following prompt:

"Let $R$ be the region in the first quadrant enclosed by the graph of $f(x)=\sqrt{\cos(x)}$, the graph of $g(x)=e^x$, and the vertical line $x=\frac {\pi}{2}$, as shown in the figure below. Region $R$ is the base of a solid whose cross sections perpendicular to the $x$-axis are semicircles with diameters on the $xy$-plane. Write, but do not evaluate, an integral expression that gives the volume of this solid."

I'm a bit confused about how I'd go about even starting a problem like this. I understand that in order to find the volume of a solid like this that I'd have to integrate the area formula with some bounds, but I'm a bit lost about what this equation would look like here. Any help would be appreciated!

答:
The diameter is between the two given curves so the radius of the semicircle is

$r = \displaystyle \frac{e^x - \sqrt{\cos x}}{2} $

Bound of $x$ is $0 \leq x \leq \frac{\pi}{2}$. Finally the range of $\theta$ is $\pi$ as cross-sections are semicircles.

So the integral is $\displaystyle \int_0^\pi \int_0^{\pi/2} \int_0^{\frac{e^x - \sqrt{\cos x}}{2}} r \ dr \ dx \ d\theta$

Title: Quick Circle Cross Sections Question


问:
Obtaining total population using Taylor series
I want to use formula
$$P(M)=\int_{0}^{M}\left[2\pi x D(x) \right]dx$$

to calculate total population living within a mile. We are given
$$D(x)=\dfrac{1}{1+0.5x^{2}}$$
Now the question first asked to obtain the $6$th degree polynomial of $2\pi x D(x)$, so first obtained the $6$th degree polynomial for
$$\dfrac{1}{1+0.5x^{2}}$$
and got
$$\dfrac{1}{1+0.5x^{2}}=1-\dfrac{1}{2}x^{2}+\dfrac{1}{4}x^{4}-\dfrac{1}{8}x^{6}$$

then I did this:
$$2\pi x D(x)=2\pi x \bigg(1-\dfrac{1}{2}x^{2}+\dfrac{1}{4}x^{4}-\dfrac{1}{8}x^{6} \bigg) $$

and got
$$2\pi x D(x)=1000\pi \bigg[ x - \dfrac{1}{2}x^{3}+\dfrac{1}{4}x^{5}-\dfrac{1}{8}x^{7} \bigg]$$

so now when I wanted to calculate the population within one mile I get:
\begin{align*}
 P(1)=1000\pi \int_{0}^{1} \bigg[ x - \dfrac{1}{2}x^{3}+\dfrac{1}{4}x^{5}-\dfrac{1}{8}x^{7} \bigg] \; dx =1259
\end{align*}

which I think is wrong. The answer is supposed to be $13090$, from a solution manual this was the answer:
\begin{align*}
 P(1)=1000\pi \int_{0}^{1} \bigg[ x - \dfrac{1}{2}x^{3}+\dfrac{1}{4}x^{5}\bigg] \; dx =13090
\end{align*}

notice that the term $-\dfrac{1}{8}x^{7}$ is missing, which I don't understand why. The question asked to obtain the $6th$ degree polynomial for $2\pi x D(x)$ and the manual wrote:
$$2\pi x D(x)=1000\pi \bigg[ x - \dfrac{1}{2}x^{3}+\dfrac{1}{4}x^{5} \bigg]$$

why did we eliminate the $-\dfrac{1}{8}x^{7}$ term? What did I do wrong?

答:
Because you want a 6th degree polynomial approximation of $xD(x)$, which should not contain the $x^7$ term.

Otherwise, you get a polynomial of degree $7$ for $xD(x)$.

Notes.

"the question first asked to obtain the 6th degree polynomial of $2()$", not a 6th degree polynomial of $D(x)$.


问:
Number of integers $a$ that satisfy $a^n \equiv a \pmod{b}$, where $b = pq$?
Prove that the number of $a$ which satisfy:

$$
a^n \equiv a \pmod{b},
$$where $b = pq$, $\quad$$p,q$ primes.

is $[\text{gcd}(n-1,p-1)+1] \cdot [\text{gcd}(n-1,q-1)+1]$

Attempt:
Since $p,q$ are coprime, then it is equivalent to find the number of $a$ which satisfy:
\begin{align}
a^n &\equiv a \pmod{p} \iff  a^{n-1} \equiv 1 \pmod{p} \tag{1}\\
a^n &\equiv a \pmod{q} \iff  a^{n-1} \equiv 1 \pmod{q}\tag{2}
\end{align}

From here, I can't figure out why the number of $a$ which satisfy $(1)$ for example, is $\text{gcd}(n-1,p-1)$ (the $+1$ part in the result must be that you have to count $0$). Any help would be appreciated.

答: If you know some basic field theory: Since $\mathbb{F}_p=\mathbb{Z}/p\mathbb{Z}$ is a finite field, $\mathbb{F}_p^{\times}$ is cyclic. Let $\alpha$ be a generator and let $d= \gcd(n-1,p-1)$. Then, by Bezout's identity, $a^{n-1}\equiv 1 \pmod{p}$ if and only if $a^d \equiv 1 \pmod{p}$. Now, note that $\beta=\alpha^{\frac{p-1}{d}}$ has order exactly $d$. That is, the subgroup $<\beta>$ has exactly $d$ elements, each a solution of $x^d\equiv 1$. So, we have at least $\gcd(p-1,n-1)$ solutions. Suppose $a$ is any other solution of $x^d\equiv 1$. Let the order of $a$ be $r$; so $$ is a subgroup of order $r$. But since $r$ must divide $d$, there exists a subgroup of order $r$ within $<\beta>$. Since a cyclic group contains a unique subgroup of each order, it must be that $a\in <\beta>$. Thus, there are exactly $\gcd(n-1,p-1)$ solutions.

Body: If you know some basic field theory: Since $\mathbb{F}_p=\mathbb{Z}/p\mathbb{Z}$ is a finite field, $\mathbb{F}_p^{\times}$ is cyclic. Let $\alpha$ be a generator and let $d= \gcd(n-1,p-1)$. Then, by Bezout's identity, $a^{n-1}\equiv 1 \pmod{p}$ if and only if $a^d \equiv 1 \pmod{p}$. Now, note that $\beta=\alpha^{\frac{p-1}{d}}$ has order exactly $d$. That is, the subgroup $<\beta>$ has exactly $d$ elements, each a solution of $x^d\equiv 1$. So, we have at least $\gcd(p-1,n-1)$ solutions. Suppose $a$ is any other solution of $x^d\equiv 1$. Let the order of $a$ be $r$; so $<a>$ is a subgroup of order $r$. But since $r$ must divide $d$, there exists a subgroup of order $r$ within $<\beta>$. Since a cyclic group contains a unique subgroup of each order, it must be that $a\in <\beta>$. Thus, there are exactly $\gcd(n-1,p-1)$ solutions.


问:
Is there some sort of function transformation expressing $(X\implies Y)\Leftrightarrow (\neg X\lor Y)$?
Is there a functional interpretation if the replacement for for the material implication?:

$$(X\implies Y)\Leftrightarrow (\neg X\lor Y)$$

Given a function from type $X$ to type $Y$, viewed as a witness of the proposition $X\implies Y$, can I obtain a proof for $\neg X\lor Y$? The connective "$\lor$" gets translated to a pair - I fail to see how this relates to a function/process, something which doesn't even require a proof of $X$.

答: It took me a while to find the post, but Neighborhood of Infinity's Exceptions, Disjunctions, and Continuations describes this topic. I haven't fully understood everything presented there, but the author asks about the isomorhism between $a \to b$ and $\lnot a \lor b$, what the type $\lnot a$ means ($a \to \bot$), and what $\lnot\lnot a$ means ($(a \to \bot) \to \bot$), and so on.  I'm not sure whether it will answer your question or not, but it might prove a useful starting point for you, or some other answer-ers.</p>


问:
Check if a point is in the interior of the convex hull of some other points in high dimensions, and lower-bounding the largest enclosed ball
Given $m$ points $P=\{p_0, p_1, ..., p_m\}$ in high dimensions (e.g. 100), it is known that computing (or even representing) their convex hull $\text{conv}(P)$ is generally intractable due to the exponential dependence on dimensions. In this case, I wonder:

Is there an efficient algorithm to check whether some other given point $\tilde{p}$ is an interior point in the convex hull (i.e. there is a small ball centered at $\tilde{p}$ and lies in $\text{conv}(P)$)? I know we can construct a linear programming problem to check if a point lies inside the convex hull, but my question here is to further check if the convex hull has "volume" and if $\tilde{p}$ lies in its interior.

Following 1, can we compute or efficiently lower-bounding the largest enclosed (inscribed) ball centered at $\tilde{p}$ and lies in $\text{conv}(P)$?

I'm an amateur in geometry and I appreciate any potential solutions or suggestions. Thank you for your time!

The same question posted on mathoverflow.

答: Does the interior point algorithm finds an ellipsoid as the result? I mean we can define a convex program with being in convex hull of $P_i$s and objective function as the distance between the variable point and $\tilde{p}$. The interior point algorithm on this mathematical program will return an ellipsoid, if possible?


问:
Exercise on bounded operator on L2 space

Let $H = L^2([0,3])$ and let $T \in B(H)$ defined by: $$Tu(t) =
 (1+t^2)u(t)$$ $||T||_{op} = 10$.

i) Is T compact? Justify the answer.

ii) Does $T$ have eigenvalues? Justify the answer.

If you may help me even on just one point this would be very helpfull really.
Thanks!

答:
Hints:

$i).\ $ Scale to $[0,1]$ and note that $\{e^{int}\}_{n\in \mathbb Z}$ is an orthonormal basis. Now show that the sequence defined by $f_n(t)=(1+t^2)e^{int}$ has no Cauchy subesequence.

$ii).\ $ Note that $Tf(t)-\lambda f(t)=0\Leftrightarrow (1+t^2)f(t)=\lambda f(t)$


问:
Lift of finite group action on circle to double cover
Suppose we have a finite group G acting on the circle.
The circle has a double cover, corresponding to the subgroup $2\mathbb{Z}$ of the fundamental group $\mathbb{Z}$ of the circle. We can lift the group action to the double cover, obtaining an an action of some central extension $\tilde{G}$ of G by $\mathbb{Z}_2$. My question is: when is $\tilde{G}$ a direct product $\tilde{G}\simeq G\times\mathbb{Z}_2$?

答:
For each $g \in G$ you have given me a diffeomorphism $\rho_g: S^1 \to S^1$. Now choose a lift $\overline \rho_g: S^1 \to S^1$ so that $\rho_g(z) = [\overline \rho_g(z^2)]$, that is, $\overline \rho_g$ is a double cover of $\rho_g$.

This gives you a 2-cocycle in $H^2(G; \Bbb Z/2)$, by $f(g,h) = \overline \rho_g \overline \rho_h (\overline \rho_{gh})^{-1}$. By the assumption that the $\overline \rho_g$ double-cover $\rho_g$, and the fact that $\rho_g$ is a group action, this expression reduces (in the quotient) to the identity. It follows that this expression is either the identity or the antipodal map, which we can think of as being an element of $\Bbb Z/2$. It is straightforward to check that this is indeed a cocycle.

Your central extension is trivial iff this group cohomology class is zero.

In many circumstances you can guarantee that this group cohomology class is zero simply because that cohomology group is zero. This is true automatically for any group of odd order (for which an extension with fiber $\Bbb Z/2$ automatically splits as a product, central or no). Sometimes you may find that this group is zero by some explicit calculation

Assuming $G$ is finite, the universal coefficient theorem gives a homological condition that is necessary and sufficeient for $H^2(G;\Bbb Z/2)$ to be zero is as follows.

You require both
i) $G^{\text{ab}}$ has no 2-torsion.
ii) The Schur multiplier, which may be calculated explicitly from a presentation due to work of Hopf, is odd order.

If $G$ has finitely generated homology groups, (but is not necessarily finite), then the first condition is unchanged but the second condition is replaced by: "The Schur multiplier is finite of odd order"; finiteness is no longer automatic.

For general $G$ you must write the conditions less explicitly: $\text{Ext}(G^{\text{ab}}, \Bbb Z/2) = 0$ and $\text{Hom}(H_2(G;\Bbb Z), \Bbb Z/2) = 0$.


问:
Why is Killing form $ad$-invariant?
How can one prove the Killing form given by $B(X,Y)=Tr(ad(X) \circ ad(Y))$, where $X,Y \in \mathfrak{g}$ and $Tr$ is the trace, is $ad$-invariant. I mean, it verifies:

$B(ad(X)(Y),Z)+B(Y,ad(X)(Z))=0$, with $ad$ the adjoint representation of Lie algebras and $ad(X)(Y)=[X,Y]$,

Applying two times the Jacobi identity to $[Z,[X,[Y,W]]]$, I got:

$ad(Z) \circ ad(X) \circ ad(Y)=ad(ad(Z)X) \circ ad(Y)+ad(X) \circ ad(ad(Z)Y)+ad(X) \circ ad(Y) \circ ad(Z)$

Then I tried to apply the trace, but I do not achieve what I want. Some ideas? Is there an easier way to do it?

答:
For any representation $\rho\colon \mathfrak{g}\rightarrow \mathfrak{gl}(V)$ we have
\begin{align*}
B_{\rho}([x,y],z) & = {\rm tr} (\rho([x,y])\rho(z)) \\
  & = {\rm tr}(\rho(x)\rho(y)\rho(z))-{\rm tr} (\rho(y)\rho(x)\rho(z)) \\
  & = {\rm tr}(\rho(y)\rho(z)\rho(x))-{\rm tr} (\rho(y)\rho(x)\rho(z)) \\
  & = {\rm tr}  (\rho(y) \rho ([z,x])) \\
  & = - B_{\rho}(y,[x,z]).
\end{align*}
So the Killing form is $\rho$-invariant. Now take $\rho=\operatorname{ad}$.

Title: Why is Killing form $ad$-invariant?


问:
Choice of numbers in calculating $\lim_{x\rightarrow 0}\frac{e^{2x}-1}{\sin 3x}$
I'm studying the limits to $\lim_{x\rightarrow 0}\frac{e^{2x}-1}{\sin 3x}$. According to my text book, I should calculate it like this:

$$\frac{e^{2x}-1}{\sin 3x} = \frac{e^{2x}-1}{2x} \times \frac{3x}{\sin 3x} \times \frac{2}{3} \rightarrow 1 \times 1 \times \frac{2}{3}$$

While it makes sense, I don't understand the use of 2 and 3. Wouldn't any other numbers make as much sense? Why are these chosen and how?

答: Easier, use Taylor series expansion around 0: $e^{2x} =1+2x+2x^2 +O(x^3), \ \sin 3x = 3x-\frac{9x^3}{2} + O(x^5)$. Plug in this expansion into your expression, do a bit of algebra and the result easily comes out.</p>


问:
Covering compact convex $-C \subseteq \mathbb{R}^d$ with $x+dC$ for some $x \in \mathbb{R}^d$: counterexample?
From Matousek's Lectures in Discrete Geometry:

Let $C$ be compact convex in $\mathbb{R}^d$. Prove that there is a suitable translation of $C$ blown up by a factor of $d$ which covers the reflection of $C$; that is, show there is an $x \in \mathbb{R}^d$ such that $-C \subseteq x + dC$.

I am confused by this question. Consider the following:

Then the reflection of this $C$ will be oriented in a different direction than $C$, and I don't see how it blown up by a factor of $2$ will make it able to cover $-C$. The greatest vertical distance between points in $2C$ is $20$, while the greatest vertical distance of between two points in $-C$ is $110$.

Am I misunderstanding the question? Or is this a counterexample?

答:
I'm not sure why you think that the greatest vertical distance between two points in $-C$ is $110$; it should just be $10$, same as $C$.

Here is a diagram showing a scaled copy of $C$ overlaid on $-C$:


答: The equation claims the area of the centre-$O$ radius-$r$ circle is $r$ times the half/circumference due to its upper semicircle, i.e. $\pi r^2=r\cdot\tfrac12\cdot2\pi r$, which is trivial if you know the semicircle's area is $\tfrac12\pi r^2$. The challenge at hand is to prove this by IBP instead. First write the problem as$$\int_{-r}^r2\sqrt{r^2-x^2}dx=\int_{-r}^r\frac{r^2}{\sqrt{r^2-x^2}}dx.$$Now integrate$$2\sqrt{r^2-x^2}=\sqrt{r^2-x^2}-\frac{x^2}{\sqrt{r^2-x^2}}+\frac{r^2}{\sqrt{r^2-x^2}}=\left(x\sqrt{r^2-x^2}\right)^\prime+\frac{r^2}{\sqrt{r^2-x^2}}.$$

Title: How to show two identical integrals $\; 2\int_{-r}^{r}f(x)dx=r\int_{-r}^{r}\sqrt{1+(df/dx)^{2}}dx$

Body:
With
$$ \;f(x)=(r^2-x^2)^{1/2}$$

show that$$\; 2\int_{-r}^{r}f(x)dx=r\int_{-r}^{r}\sqrt{1+(df/dx)^{2}}dx$$

by using integration by parts. Then, conclude that the area of a circle of radius r is $\;\pi r^2$ if we define $\;\pi=\;$ circumference$\;\div\;$ diameter

I thought the only method I can use is via trig substitutions. But, the problem asks to solve it with integration-by-parts.

I need help to solve this problem.
Thank you.


问:
Find integral from a known integral

The correct answer is $7$. I figured out that if you substitute the inner argument of the second function, the end points become the same but flipped. That means we can just negate the integral and get the same endpoints. This is where I am now stuck. How do I get to the result with that knowledge?

Title: Find integral from a known integral

Body:
First, let $u = 7 - 8x$. Then, $u(0) = 7$ and $u(19) = -145$. Also, $dx = -\frac{du}{8}$. Then, we wish to calculate:

$$\int_{0}^{19}f(7-8x)\ dx = \int_{u(0)}^{u(19)}-f(u)\ \frac{du}{8} = -\frac{1}{8}\int_{7}^{-145}f(u)\ du = \frac{1}{8}\int_{-145}^{7}f(u)\ du =\frac{56}{8} = \boxed{7}$$


问:
Questions about elliptic fibrations
Say I have an algebraic surface $S$ (smooth, projective over $\mathbb{C}$) and a morphism $f: S \to B$ to some curve $B$ (smooth, projective over $\mathbb{C}$) defined by the complete linear system corresponding to some divisor $D$ on $S$. We assume this linear system to be base point free.

Is it true that $D$ will be a sum of fibres of $f$ and if so, why?

In fact I'm just trying to understand the proof of Proposition IX.2.(b) in Beauville's book on algebraic surfaces. The proof goes as follows:

(Here $S$ is a smooth projective surface over $\mathbb{C}$ with $\kappa(S) = 1$. Moreover, $M$ is some effective divisor such that $|M|$ is base point free - corresponding to the mobile part of $|nK_S|$ for some $n$ such that the $n$-th plurigenus is at least $2$ - and $K \cdot M = 0$ where $K$ is the canonical divisor.)

"(...) It follows that $|M|$ defines a morphism $f$ from $S$ to $\mathbb{P}^N$ whose image is a curve $C$. Consider the Stein factorization $f: S \to B \to C \subseteq \mathbb{P}^N$, where $p: S \to B$ has connected fibres. Let $F$ be a fibre of $p$. Since $M$ is a sum of fibres of $p$ and $K \cdot M = 0$, we must have $K \cdot F = 0$. (...)"

There are three statements which are not clear to me:

*Why should $M$ be a sum of fibres of $p$?

*Why does $K \cdot M = 0$ imply that $K \cdot F = 0$ for ANY fibre $F$?

*Why on earth should the curve $B$ coming out of this construction be smooth? I mean, all we did is starting with a smooth, projective surface $S$ with $\kappa(S) = 1$, taking the mobile part of the linear system $|nK_S|$ for some $n$ such that the $n$-th plurigenus is $\geq 2$ (which is base point free), giving a curve $C$  which is the image of the corresponding pluricanonical map, and then taking the curve $B$ coming out of the Stein factorization. I see no reason why $B$ should be smooth, I'm really lost here.

On a related note, in the proof of Proposition IX.3:

"(...) Let $S$ be a minimal elliptic surface. Since $K_S \cdot F_b = 0$ for all $b \in B$, the maps contract the fibres $F_b$. It follows that the image of $\varphi_{nK}$ has dimension $\leq 1$. (...)"

Why is this true?

答:
Here's an attempt to clarify the three statements.

Why should $M$ be a sum of fibres of $p$?

$f=\varphi_M$ is the morphism associated to $|M|$ and $f$ factorizes with $p$ plus an embedding of the curve, so geometrically you have to think of the fibers of $p$ as fibers of $f=\varphi_M$. Now, the condition $M^2=0$ geometrically means that the curves in $|M|$ are vertical: indeed a fiber of $p$ (read: of $f$) will be an element in $|M|$, and has self-intersection zero. In other words the components of $M$ are contained in some fibers of $p$. In symbols this means we can write
$$ M=\sum r_F F $$
where $r_F\geq 0$ and $F$ are the fibers of $p$.

Why does $K \cdot M = 0$ imply that $K \cdot F = 0$ for ANY fibre $F$?

Observe $K\cdot F\geq 0$ for any fiber since $K$ is nef. Thus
$$ 0=K\cdot M=\sum r_F K\cdot F $$
which gives $K\cdot F=0$.

Why on earth should the curve $B$ coming out of this construction be smooth?

Yes, it could also be singular. If that's the case then just replace $B$ with its desingularization. You still have your morphism $p:S\rightarrow B$ onto a smooth curve, with the desired properties.

Hope that helps :)

Title: Questions about elliptic fibrations


问:
Rank one matrix
Given that I know that the matrix $\mathbf{W} \in \mathbb{R}^{d \times m}$ satisfies that:
$$\mathbf{W}^\top\mathbf{W} = \mathbf{a} \cdot \mathbf{a}^\top$$
Where $\mathbf{a} \in \mathbb{R}^{m \times 1}$ is a column vector.

Does this mean $\mathbf{W}$ is a rank one matrix, meaning it's columns are all identical up to some multiplicative scale?

答:
If $a=0$, then rank of $W$ is $0$.

Otherwise, you are right, the rank of $W$ is $1$. $$rank(W^TW)=1,$$

Let $W=U\Sigma V^T$, then $W^TW=V\Sigma^T\Sigma V^T$, and we can see that the rank of $W^TW$ and the rank of $W$ is the same.

OwnerDisplayName: ShaharA

Title: Rank one matrix

OwnerDisplayName: Siong Thye Goh


问:
How do I convert equations from cartesian to spherical/cylindrical?
I understand the relations between cartesian and cylindrical and spherical respectively. I find no difficulty in transitioning between coordinates, but I have a harder time figuring out how I can convert functions from cartesian to spherical/cylindrical.

Given a multivariable function, let's say $$f(x,y)=x^2+2xy+y^2,$$ how do I convert this equation to the spherical and cylindrical?

Is there a given method I can use that will always produce a correct result? Perhaps I have not given this enough thought, but I'd like to wrap my head around this and given neither our lecturer or the literature gives any though on the matter I find myself rather lost.

答:
First of all, you have a function of two variables, $f(x,y)$, thus you might want to use polar coordinates instead of cylindrical/spherical coordinates.

You can use these formulas to convert from cartesian coordinates to polar coordinates: $$\begin{aligned}x&=r\cos\theta\\y&=r\sin\theta.\end{aligned}$$

Substituting into the given function $f(x,y)=x^2+2xy+y^2$ yields:$$\begin{aligned}f(r,\theta)&=r^2\cos^2\theta+2(r\cos\theta)(r\sin\theta)+r^2\sin^2\theta\\&=r^2(\cos^2\theta+\sin^2\theta)+2r^2\cos\theta\sin\theta\\&=r^2(1+2\cos\theta\sin\theta).\end{aligned}$$

Notice that the function $f$ now depends on $(r,\theta)$ instead of $(x,y)$.

For a function of three variables $f(x,y,z)$ one can use cylindrical coordinates:
$$\begin{aligned}x&=r\cos\theta\\y&=r\sin\theta\\z&=z\end{aligned}$$ or spherical coordinates:
$$\begin{aligned}x&=r\sin\theta\cos\varphi\\y&=r\sin\theta\sin\varphi\\z&=r\cos\theta.\end{aligned}$$
Hope this helps. :)


问:
Conditions of Convergence of complex series
Suppose $S$ is a complex series. If we want to show $S$ to be convergent, then it is sufficient to show $\mid S\mid$ is convergent. Why is this true? Why arg$(S)$ is not playing any role?

答:
A comment that got too long and which tries to explain various things involved above.

In general, the statement in the OP is ambiguous and under a reasonable interpretation is not even true. So to make it clear let $S_n=\sum_{k \le n} a_n$ the partial sums of the series, $T_n = \sum_{k \le n} |a_n|$ the partial sums of the series with absolute value terms.

So if we interpret the OP as $|S_n|$ converges implies the series converges, the result is not true in general as taking $a_n$ (which are $S_n-S_{n-1}, S_{-1}=0$ say) st $S_n=e^{2\pi i \sqrt 2 n}, n \ge 0$ shows as $|S_n|=1$ but obviously $S_n$ doesn't converge and it is actually a dense sequence in the unit circle

If we interpret the OP as $T_n$ converges, then the result is true but then the series is absolutely convergent which is a very strong form of convergence.

On the other hand, if $|S_n| \to 0$ or more generally if $|S_n-L| \to 0$ for some complex $L$, then indeed the series converges to zero or $L$ respectively and that is a possible correct interpretation of the OP.

So as to the question asked, the argument actually matters unless we have strong conditions like absolute convergence or we interpret the statement as the third choice above


答:
Since you know that the cross sections are semi-circles, you can think of splitting the volume into semi-cylindrical slabs of length $\Delta x$.  The radius of each semi-cylindrical slab is $$r = \frac{e^{x} - \sqrt{\cos(x)}}{2},$$ and so the volume is $$\frac{1}{2}\pi r^2 \Delta x = \frac{1}{2}\pi \left(\frac{e^{x} - \sqrt{\cos(x)}}{2}\right)^{2}\Delta x = \frac{1}{8}\pi \left(e^{x} - \sqrt{\cos(x)}\right)^{2}\Delta x.$$  Writing the volume as a Riemann sum:
$$V \approx \sum_{i=1}^{n} \frac{1}{8}\pi \left(e^{x_{i}} - \sqrt{\cos(x_{i})}\right)^{2}\Delta x_{i},$$ and upon taking the limit as $n\to \infty$, we get the integral $$V = \frac{\pi}{8}\int_{0}^{\frac{\pi}{2}}\left(e^{x} - \sqrt{\cos(x)}\right)^{2}\,dx.$$

Title: Quick Circle Cross Sections Question

Body:
So I was given the following prompt:

"Let $R$ be the region in the first quadrant enclosed by the graph of $f(x)=\sqrt{\cos(x)}$, the graph of $g(x)=e^x$, and the vertical line $x=\frac {\pi}{2}$, as shown in the figure below. Region $R$ is the base of a solid whose cross sections perpendicular to the $x$-axis are semicircles with diameters on the $xy$-plane. Write, but do not evaluate, an integral expression that gives the volume of this solid."

I'm a bit confused about how I'd go about even starting a problem like this. I understand that in order to find the volume of a solid like this that I'd have to integrate the area formula with some bounds, but I'm a bit lost about what this equation would look like here. Any help would be appreciated!


答:
Substituting in the second argument  you get

$$-\frac{1}{8}\int_7^{-145}f(y)dy=\frac{1}{8}\int_{-145}^{7}f(y)dy=\frac{56}{8}=7$$

Title: Find integral from a known integral

Body: The correct answer is $7$. I figured out that if you substitute the inner argument of the second function, the end points become the same but flipped. That means we can just negate the integral and get the same endpoints. This is where I am now stuck. How do I get to the result with that knowledge?


问:
Improper integral $\int_0^3 \frac{dx}{(x-1)^{2/3}}$

Determine if the improper integral converges or diverges. If it converges, find the limit.

$$\int_0^3 \frac{dx}{(x-1)^{2/3}}$$
$$=\int_0^1 \frac{1}{(x-1)^{2/3}}dx + \int_1^3 \frac{1}{(x-1)^{2/3}}dx$$
$$=\lim_{x \to 1^-} \int_0^1 \frac{1}{(x-1)^{2/3}}dx + \lim_{x\to1^+}\int_1^3 \frac{1}{(x-1)^{2/3}}dx$$

I'm confused here. Does it diverge because $\lim_{x \to 1^-} \int_0^1 \frac{1}{(x-1)^{2/3}}dx$ has an imaginary part to the left of 1?

答:
There is a potential problem at $x=1$. So break up the integral into two parts, from $0$ to $1$ and from $1$ to $3$. If both integrals converge, your original integral converges. If either integral diverges, your integral diverges.

So let us consider
$$\int_0^1 \frac{dx}{(x-1)^{2/3}}.$$
There is a matter of interpretation involved here. To some people, $u^{2/3}$ does not make sense for negative $u$. To others, it makes sense, because the denominator $3$ in the exponent is odd. To answer the question, we take the second view.

What we need to do is to let
$$I(b)=\int_0^b \frac{dx}{(x-1)^{2/3}},$$
 and find the limit (if it exists) of $I(b)$ as $b$ approaches $1$ from the left.

An antiderivative of $(x-1)^{-2/3}$ is $3(x-1)^{1/3}$. So $I(b)=3(b-1)^{1/3}-3(-1)^{1/3}$. As $b$ approaches $1$ from the left, this approaches $3$.

Do a similar calculation for the interval from $1$ to $3$.

Remark: In the reals, a standard definition of $a^b$  is $a^b=\exp(b\ln a)$. Under that definition, $a^b$ does not exist if $a$ is negative.

However, this conflicts with the usual lower level understanding that, for example, $(-8)^{1/3}=-2$, since $(-2)^3=-8$.

When $q$ is an odd integer, we can define $a^{1/q}$ as the real number whose $q$-th power is $a$. This makes sense, there is a unique such number. And then for any integer $p$, we can define $a^{p/q}$ as the $p$-th power of $a^{1/q}$. This works well for negative $a$.

We cannot make a similar definition of $a^{p/q}$ when $a$ is negative and $q$ is even.


问:
Proving that a $3$-dimensional compact polytope such that every two vertices are adjacent is a tetrahedron

So I have to prove that given a 3-dimensional compact polytope such that every two vertices are adjacent, then it is a tetrahedron.

Somehow I'm able to visualise from the fact that every two vertices are adjacent and sees that it fits to the diagram of tetrahedron. Like it is a polyhedron composed of four triangular faces, six straight edges, and four vertex corners. From this it is suffice that every other vertices is adjacent to each other. But I'm not quite sure how to prove it.

Could you please help me in proving the above statement.

Cheers.

答:
As stated, this is false; the Császár polyhedron is a counterexample.

If your polyhedron is stipulated to be topologically equivalent to a sphere, then we may apply Euler's formula of $V-E+F=2$. Suppose that our polyhedron has $n$ vertices. Then it has$\frac{n(n-1)}2$ edges, and at most $\frac{2E}3$ faces, because each face touches at least three edges and every edge is shared by two faces.

So we have

$$n-\frac{n(n-1)}2+\frac{n(n-1)}3\ge V-E+F = 2$$

It is easy to check that only for $n=3,4$ is this inequality satisfied, and as the $n=3$ case yields a degenerate polyhedron (two triangles glued back-to-back), $n=4$ is the only possibility, and only works if each face is a triangle.


问:
Determinant of identity matrix minus exponential matrix $\det(I-k \exp (M)),$
I am currently struggling with the following determinant
$$\det(I-k \exp (M)),$$
where $I$ is the $2\times2$ identity matrix, $M$ is a $2\times2$ matrix and $k$ is an arbitrary constant. Is there a general way of handling such objects?

答:
I used Wolfram Mathematica code

```<code>Det@MatrixFunction[1-k*Exp[#]&,{{a,b},{c,d}}]//FullSimplify//TeXForm
</code>```

which returns the result

$$-2 k e^{\frac{a+d}{2}} \cosh \left(\frac{1}{2} \sqrt{(a-d)^2+4 b c}\right)+k^2 e^{a+d}+1$$

and I have no reason to doubt its validity. As you can see, the
Mathematica function MatrixFunction does the hardest part of the job.

You can check the validity for diagonal matrices with

```<code>Det@MatrixFunction[1-k*Exp[#]&,{{a,0},{0,d}}]//Factor//TeXForm
</code>```

which returns
$$\left(e^a k-1\right) \left(e^d k-1\right)$$
as it should.

Body:
I used Wolfram Mathematica code

Det@MatrixFunction[1-k*Exp[#]&,{{a,b},{c,d}}]//FullSimplify//TeXForm

which returns the result

$$-2 k e^{\frac{a+d}{2}} \cosh \left(\frac{1}{2} \sqrt{(a-d)^2+4 b c}\right)+k^2 e^{a+d}+1$$

and I have no reason to doubt its validity. As you can see, the
Mathematica function MatrixFunction does the hardest part of the job.

You can check the validity for diagonal matrices with

Det@MatrixFunction[1-k*Exp[#]&,{{a,0},{0,d}}]//Factor//TeXForm

which returns
$$\left(e^a k-1\right) \left(e^d k-1\right)$$
as it should.


问:
Proving that the independent set problem is in NP-Complete
Consider the problem of "Independent set" in grahps. Given a graph $G$ and an integer $k$, the machine determines whether the graph $G$ contains an independent set of size $k$.

I need to prove that it's in NP-Complete by showing a reduction from another known language in NP-Complete (vertex cover, clique, sat) to IS problem. which one would you suggest?

Thanks in advance

答: Vertex cover. If $S$ is a vertex cover of $G$ of size $|V(G)| - k$, then the collection of vertices of $G$ not in $S$  must form an independent set (why?) of size $k$. </p>


问:
Convergence of an increasing sequence given convergence of the Cesaro sum
I’ve been playing with Cesaro summation and I’m now stuck on a problem. Given an increasing sequence $(u_n)_{n\in\mathbb{N}}$ of real numbers, define it’s Cesaro sum as $C_n = \frac{1}{n} \sum\limits_{k=1}^n u_k$. I’ve been able to prove a few facts, ie, given any $(u_n)$, if $(u_n)$ converges to $l$ then $(C_n)$ does to, $(u_n)$ bounded implies $(C_n)$ is bounded as well and $(u_n)$ increasing implies $(C_n)$ increasing.

Here since we assume $(u_n)$ increasing we know $(C_n)$ is too.
I’d like to show that if we further assume that $(C_n)$ is convergent, then $(u_n)$ is too.

My guess was to try to show that if $(C_n)$ is convergent, then $(u_n)$ is bounded, and since it’s increasing we can conclude it is convergent. This works well enough for sequences of positive real numbers, but not sure how to make it work when the sequence is necessarily non-negative. I think it’s true, though it’s not obvious why. Any help is appreciated, thank you.

答: All you have to show is that $u_{n}$ is bounded. I mean, increasing and bounded sequence is convergent. If $u_{n}$ is unbounded so is $C_{n}$. Now, convergence of $C_{n}$ implies that $C_{n}$ is bounded and so is $u_{n}$.


问:
On the greatest prime factor of $p^2+1$, $p\in\mathbb{P}$

Are there infinitely many pairs $(p,q)\in\mathbb{P}^2$ such that $p>q$ and $p\mid q^2+1$?

This is a very interesting. There are many methods for bounding the greatest prime factor of $n^2+1$, but when $n$ is a prime this gets tricky.

Full disclosure: This was originally posted on AoPS. Here are some arguments for the existance of such solutions: (credit goes to Tintarn)

A standard probabilistic heuristic would indicate that we certainly
expect infinitely many such solutions, in fact there should be roughly
$\asymp \frac{x}{(\log x)^2}$ solutions with $p,q \le x$. But proving
this is of course a completely different matter, and I don't see an
easy way to do this. This might just be an extremely hard problem,
compared with the famously unsolved problem whether $n^2+1$ is
infinitely often prime.

Any ideas, resources or implications are greately appreciated! For more information about the greatest prime factor of $n^2+1$ read these:

A lower bound for the greatest prime divisor of $n^2+1$

Greatest prime divisor of $ n^2+1$

答: A sufficient condition is that there are infinite many positive integers $\ k\ $ such that both $$10k+7$$ and $$10k^2+14k+5$$ are prime. This is a consequence of the generalized Bunyakovsky conjecture , which is however open. If we assume this conjecture to be true , because of $$(10k+7)^2+1=2\cdot 5\cdot (10k^2+14k+5)$$ we only have to set $$q:=10k+7$$ $$p:=10k^2+14k+5$$ to get a solution for every suitable $\ k\ $ , hence infinite many pairs doing the job. This is only one of many possible parametrizations we can establish. If any of them has infinite many solutions, infinite many pairs with the desired properties exist. So, the answer to the question should be "yes" although this is of course not a rigorous proof.


问:
Why is the entire set $X$ open in every topology
So I've just picked up topology and i read that for any set $X$ the entire set is an element of every topology and so is an open set.
but why is this so?
I understand that the complement of $X$ is $\emptyset$ which is open by vacuous truth however how do we then show that $X$ is open?

Thanks in advance.

答: By definition of a topology the set $X$ and $\emptyset$ will lie in it, so that they are always both open and closed.


问:
Random projection of a fixed point
In the book "High-dimensional probability by Vershynin", page 111, in the proof of Johnson-Lindenstrauss Lemma, let $E$ be a random $m$-dimensional subspace in $\mathbb{R}^n$ uniformly distributed in the Grassmannian $G_{n,m}$, i.e,

$$E \sim Unif(G_{n,m}))$$.

Denote the orthogonal projection onto $E$ by $P$. Let $z\in \mathbb{R}^n$ be a fixed point such that $||z||_2=1$.

The book intuitively claim that instead of random projection $P$ acting on a fixed vector $z$, we consider a fixed projection $P$ acting on a random vector $z\sim Unif(S^{n-1})$. Then, the distribution of $||Pz||_2$ is unchanged.

I was wondering if there is a rigorous way to show the invariance of distribution. I thin we may use the rotation invariance property of $z$.

答:
You can think of the Grassmannian as being some canonical $m$ dimensional subspace with a uniformly distributed random orthogonal transformation (i.e. it is a homogeneous space). To get this uniform distribution on the orthogonal group we use the Haar measure $\lambda$, which for any group $G$ acts like a uniform distribution on $G$. In particular, for compact groups, this measure is both left and right invariant. By this I mean that for any $g \in G$ and any measurable subset $A$ of $G$ we have $\lambda(gA) = \lambda(Ag) = \lambda(A)$. Moreover this means that if $M \sim \lambda$ then $gM \sim \lambda$. Using this on the two norm and with $G$ as the orthogonal group gives:

$||Pz||_2^2 = ||R D R^\top z ||_2^2 = ||DR^\top z||_2^2 = ||D x||_2^2$

where $R \sim \lambda$, $D$ is a fixed diagonal projection matrix and $x = R^\top z$ is uniform on the sphere. (There is a property called unimodularity that means that $R^\top \sim R$.)

Title: Random projection of a fixed point


问:
A countable elementary submodel of $L_{\omega_1}$
Let $N \prec \left(L_{\omega_1}, \in\right)$ be a countable elementary submodel.

In Jech Set Theory he states:

$N$ is transitive. Let $X\in N$. Let $f$ be the $<$-least mapping of $\omega$ onto $X$. Since $f$ is definable in $(L_{\omega_1}, \in)$ from $X$, $f$ is in $N$. Hence $f(n)\in N$ for all $n<\omega$ and we get $X\subset N$.

What I don't understand is the way $f$ is chosen and the reasoning behind why it is definable and how.

Can you apply the above to an elementary submodel $N\prec L_{\omega_2}$ s.t $|N|=\aleph_0$?

答:
One of the main points of the argument is that every object in $L_{\omega_1}$ is countable internally. (Of course, $\omega_1=\omega_1^L$ in this problem.) That is, $L_{\omega_1}$ catches every set in itself is countable. Since $N\prec L_{\omega_1}$, $N$ also thinks every object is countable.

Thus this argument does not work if we replace $\omega_1$ with other ordinals, like $\omega_2$: every countable elementary submodel of $L_{\omega_2}$ would think there is an uncountable set, although it could not be a genuine uncountable set.

I explained why $f$ is definable in the comment, but let me summarize the point: $L_{\omega_1}$ thinks there is a definable global well-order (namely $<_L$.) Thus $N$ also thinks there is a global well-order which is definable. Hence the formula

$$\phi(f) :\equiv [f\text{ is onto from $\omega$ to $X$ and $f$ is the $<_L$-least function among them}]$$
is a first-order formula which defines an object (which is a function we desire.)


问:
Why does $\int_{e}^{+\infty} \frac{(\ln x)^{-100}}{x} d x = 1/99$?
To find the improper integral $\int_{e}^{+\infty} \frac{(\ln x)^{-100}}{x} d x$ after substitution we get $\int_{1}^{\infty}t^{-100}dt$ and thus

$\int_{e}^{+\infty} \frac{(\ln x)^{-100}}{x} d x=-\left.\frac{1}{99} \lim _{y \rightarrow+\infty} t^{-99}\right|_{1} ^{y}=-\frac{1}{99} \frac{1}{1^{99}}-(-\frac{1}{99}\cdot \lim_{y \to \infty}\frac{1}{y^{99}})=-\frac{1}{99} + \frac{1}{99}\cdot 0=-\frac{1}{99}$.

However the official solution is $1/99$. So are they wrong or is there an error in my reasoning?

Intuitively the official solution makes sense, since we are integrating a function that is strictly positive on the interval. But algebraically I can't make any sense of it.

答: You've made a simple sign error.  We have $$\int_{t=1}^\infty t^{-100} \, dt = \left[-\frac{1}{99} t^{-99} \right]_{t=1}^\infty = \frac{1}{99} \left( 1^{-99} - \lim_{t \to \infty} t^{-99} \right) = \frac{1}{99} (1 - 0) = \frac{1}{99}.$$  Note that in the third expression, we have cancelled the negative sign in front of $-1/99$ by reversing the order of evaluation, with $t = 1$ first and $t \to \infty$ second.


问:
BMO2 2020 Question 4
So I attempted the 2020 paper for BMO2 (https://bmos.ukmt.org.uk/home/bmo2-2020.pdf), but I've been stuck on Q4.

A sequence $b_1,b_2,b_3,...$ of non-zero real numbers has the property that $b_{n+2}=\frac{b^2_{n+1}−1}{b_n}$ for all positive integers n. Suppose that $b_1=1$ and $b_2=k$ where $1<k<2$. Show that there is some constant $B$,depending on $k$, such that $−B≤b_n≤B$ for all $n$. Also show that, for some $1<k<2$, there is a value of $n$ such that $b_n>2020$.

The only idea that came to mind was to try and solve for an nth term (which I could not do) or to use induction to prove the existence of bounds, which doesn't seem to work out since we have the division.

Looking online I found someone's solution, in which they gave the nth term as
$$ b_n = \frac{\sin(n\gamma)}{\sin(\gamma)} $$
where $\gamma = \arccos(k/2)$
And from here it's trivial.

However they did not say how they derived this formula apart from "intuition". The only intuitive link I see between the nth term and the recurrence is that both feel "bouncy".

The only method I can think of that would be helpful here is generating functions, but as far as I'm aware they cannot help when we have products of sequences except for the special case of convolutions and convolutions multiplied by binomial coefficients.

So my questions are:

How could you derive this nth term?

Does this fit into a larger pattern of recurrence relations that can be solved using slightly "squished" trig function?

How could this be solved using only elementary mathematics? (As the competition is intended so every question can, at least in theory, be done using clever tricks without higher maths (given that the question did not ask for an nth term, I presume there is a method to solve this that does not actually require finding one)

答:
A while ago somebody posted a similar question (or maybe the same) but I forgot where it was.

$$b_{n+2} b_n = b_{n+1}^2 - 1, b_{n+1} b_{n-1} = b_n^2 - 1\\
\implies b_{n+1}^2-b_{n+2}b_n = b_n^2-b_{n+1}b_{n-1}\\
\implies b_{n+1}(b_{n+1}+b_{n-1})=b_n(b_n+b_{n+2})\\
\implies \frac{b_{n+1}+b_{n-1}}{b_n}=\frac{b_{n+2}+b_n}{b_{n+1}}$$

Therefore $$\frac{b_{n+1}+b_{n-1}}{b_n} \equiv \frac{b_3+b_1}{b_2}=\frac{k^2-1+1}{k}=k\\
\implies b_{n+1}=k b_n-b_{n-1}$$

This is a second order linear difference equation with characteristic function $\lambda^2-k\lambda+1=0$ which has two complex roots. So you can follow this link to get the solution which then would have the trig term.

Title: BMO2 2020 Question 4


问:
Reduce to lowest possible gates
I am trying to reduce (¬A V ¬B) V (A ⊕ B ) to be expressed by the lowest possible number of gates. So far by expanding the XOR gate and using Demorgan's and distributive laws, I have come down to this
¬(A ∧ B) V (A V B)
Is it possible to reduce this even further?</p>

答: $\overline A+\overline B +A \oplus B = \overline A+\overline B +\overline A B + A\overline B=\overline A(1+B)+\overline B(1+A)=\overline A+\overline B=\overline {AB}$

Title: Reduce to lowest possible gates


答:
Given a set $X$, a topology is a collection of subsets of $X$ that satisfy some "axioms". Those axioms define what a topology is on $X$. One of those axioms says that both $X$ and the empty set are in the topology. This is how you "show" that $X$ is always open with respect to any topology.

Given any set $X$, it has the trivial topology which consists of only the empty set and the entire set $X$.

Notes.

It is a reasonable question to ask why those axioms, for instance why the whole space is always assumed to be open in the axioms. You may want to read this question:
Why the axioms for a topological space are those axioms?

Title: Why is the entire set $X$ open in every topology

Body:
So I've just picked up topology and i read that for any set $X$ the entire set is an element of every topology and so is an open set.
but why is this so?
I understand that the complement of $X$ is $\emptyset$ which is open by vacuous truth however how do we then show that $X$ is open?

Thanks in advance.


Title: Why does $\int_{e}^{+\infty} \frac{(\ln x)^{-100}}{x} d x = 1/99$?

Body:
To find the improper integral $\int_{e}^{+\infty} \frac{(\ln x)^{-100}}{x} d x$ after substitution we get $\int_{1}^{\infty}t^{-100}dt$ and thus

$\int_{e}^{+\infty} \frac{(\ln x)^{-100}}{x} d x=-\left.\frac{1}{99} \lim _{y \rightarrow+\infty} t^{-99}\right|_{1} ^{y}=-\frac{1}{99} \frac{1}{1^{99}}-(-\frac{1}{99}\cdot \lim_{y \to \infty}\frac{1}{y^{99}})=-\frac{1}{99} + \frac{1}{99}\cdot 0=-\frac{1}{99}$.

However the official solution is $1/99$. So are they wrong or is there an error in my reasoning?

Intuitively the official solution makes sense, since we are integrating a function that is strictly positive on the interval. But algebraically I can't make any sense of it.

Body:
$$I=\int_{e}^{\infty} \frac{(\ln x)^{-100}}{x} dx$$
Let $x=e^t$
$$I=\int_{1}^{\infty} t^{-100} dt= \int_{1}^{\infty} \frac{t^{-99}}{-99}|_{1}^{\infty}=\frac{1}{99}.$$


问:
Aces and eights game
The following is an exercise from the book: Reasoning about Knowledge by R.Fagin, J.Y. Halpern, Y. Moses, M.Y. Vardi.

I have been trying for some time to crack it but still unable to find a simple approach to solve it. Any suggestions are appereciated.

Consider a game which is played with a deck consisting of four aces and four eights. There are three players. Six cards are dealt out, two to each player. The remaining two cards are left face down. Without looking at the cards, each of the players raises them up to his or her forehead, so that the other two players can see
them but he or she cannot. Then all of the players take turns trying to determine which cards they’re holding (they do not have to name the suits). If a player does not know which cards he or she is holding, the player must say so. Of course, it is common knowledge that none of you would ever lie, and that all players are perfect reasoners.

Show that there exists a situation where only one of the players will be able to determine what cards he or she holds, and the other two will never be able to determine what cards they hold, no matter
how many rounds are played.

It is relatively simple to see that at least one player will detarmine her/his own cards the as it seems key cases are:

$AA,88,A8$ - third player determines his/her cards since first and second players can nonot determine theyr cards $AA,88$ are impossible.

$A8,88,A8$ - first player determines his/her own cards on second move.

$A8,A8,A8$ - second player determines his/her cards on second move.

All other cases are reducible to the three to see that at least one will determine his/her cards at some move.

But I can not find the case when the remaining two can not determine their cards in any number of moves. I don't see a structure which gives this.

It seems that $A8,88,A8$ and $A8,AA,A8$ are such situations that second and third player can not decide which cards they have, am I right?

Can players 1 and 2 distinguish $AA,88,A8$ from $AA, AA, 88$?

答:
[EDIT: The simplification I apply below fundamentally alters the game, so cannot really tell us anything about the original game. See BartBog's answer for why.]

I agree with you.

It is easier to amend the game slightly, so that in a round all three players reveal their pronouncement at the same time, independent of one another. This simplifies the reasoning because it is no longer turn based, so the order of the players no longer matters.

I think that this version is equivalent in the sense that in the end the same conclusions will be reached by the players. If you compare a single round of this version with one round around the table of the original, the players have less information to base their deductions on, so this version is at least as hard for the players as the original. On the other hand, comparing a single player's turn of the original to one round of the new version shows that more information is revealed in the new version, so the original is at least as hard as the new one. I'm not totally convinced that reasoning is valid (Edit:- It isn't!) , but for now lets assume it is.

In this simultaneous-play version of the game, deductions will be as follows:

Round 1:
If all players have a pair (AA or 88), then one player will see four the same cards and know their hand. If that happens, the other two players will be able to deduce their hand and announce it in the next round.

If no one deduces their hand, this round eliminates the no-mixed-hand cases AA/AA/88 and AA/88/88.

Round 2:
If any player sees two pairs (AA and 88), then they will know they have a mixed pair (A8). If that happens, the other two players will be able to deduce their hand and announce it in the next round.

If no one deduces their hand, this round eliminates the one-mixed-hand case AA/88/A8.

Round 3:
If a player sees one pair (AA/A8 or 88/A8), then they will know they have a mixed hand (A8). If that happens it will be to two players, but the player with the matched pair will not know whether he has AA or 88.

If no one deduces their hand, this round eliminates the two-mixed-hand cases AA/A8/A8 and 88/A8/A8.

Round 4:
Now everyone knows it must be the three-mixed-hand case A8/A8/A8, and all players deduce their hand.

So at worst one player cannot deduce their hand because they see A8/A8 and can have either AA or 88.

Title: Aces and eights game


问:
How to show uniqueness(!) of square-free $d \in \mathbb{Z}$ such that $\mathbb{Q}(\sqrt{d}) = K $ for a quadratic number field $K$?
I already know a proof for the existence of such a $d$, but am looking for a proof of its uniqueness.

There is a good answer in Lemma 2 of the linked post. But I was wondering whether there is a more elementary proof, which perhaps does not use the trace mapping.

答:
If $\mathbb{Q}(\sqrt{d}) = \mathbb{Q}(\sqrt{d'})$, with $d,d'$ squarefree integers, then there exist $r,s\in\mathbb{Q}$ such that $\sqrt{d}=r+s\sqrt{d'}$. Squaring both sides we get
$$d = r^2+s^2d' + 2rs\sqrt{d'}.$$
That means that $rs=0$. If $r=0$, then writing $s=\frac{a}{b}$, $a,b\in\mathbb{Z}$, $\gcd(a,b)=1$, we have
$$\begin{align*}
d &= s^2d'\\
b^2d &= a^2d'.
\end{align*}$$
Thus, $b^2|a^2d'$. Since $\gcd(b^2,a^2)=1$, $b^2|d'$. Since $d'$ is squarefree, $b^2=1$. Thus, $s=a\in\mathbb{Z}$. But then $d=a^2d'$, and since $d$ is squarefree, $a^2=1$. Thus, $d=d'$.

If $s=0$, we get $d=r^2$, and since $d$ is squarefree this means $d=1$. But then $\mathbb{Q}(\sqrt{d'}) = \mathbb{Q}$, so $\sqrt{d'}\in\mathbb{Q}$, which means $d'$ is a square; being squarefree, we have $d'=1=d$.


问:
Prove that if $\lim_{n\to+\infty} a_n = +\infty$ then $\lim_{n\to+\infty} \frac{a_1+a_2+...+a_n}{n} = +\infty$
I have to prove a problem, I arrived to a solution but I don't know it is correct.

The problem:

Prove that if
$$\lim_{x\to+\infty} a_n = +\infty$$

Then

$$\lim_{n\to+\infty} \frac{a_1+a_2+...+a_n}{n} = +\infty$$

I thought about doing this similarly to how you prove Ernesto Cesaro's theorem.

By definition

$$\forall M\gt0 \quad \exists n^*: \forall n \gt n^* \quad a_n > M $$

Now I have

$$\frac{a_1+a_2+...+a_{n^*-1}+a_{n^*}+...+a_n}{n}$$

The first part of the fraction can be replaced with

$$S=\frac{a_1+a_2+...+a_{n^*-1}}{n}$$

And then I have all the terms next to $a_{n^*}$ greater than $M$

$$\frac{a_{n^*}+...+a_n}{n} \gt \frac{(n-n^*)M}{n} $$

$$\frac{a_1+a_2+...+a_{n^*-1}+a_{n^*}+...+a_n}{n}\gt S+\frac{(n-n^*)M}{n}$$

Then I choose $M^*$

$$M^*=S+\frac{(n-n^*)M}{n}$$

I have at the end that

$$\frac{a_1+a_2+...+a_n}{n} \gt M^*$$

You can choose whatever $M$ you want, so the problem is proved.

I don't really know if the proof is rigorous, I tried to use that path and I hope that there could be at least something decent in there.

In the case the proof is not valid, I ask you if you can give some tip on where to start to prove it.

答:
You almost ended the problem. You can suppose that all the elements of the sequence are positive (if not it is enough to add some fixed positive constant to every element of the sequence), so $S>0$. So from what you said, for every $M>0$ you have $n^*$ such that for all $n>n^*$,

$\frac{a_1+a_2+...+a_n}{n}\geq S+\frac{(n-n^*)}{n}\cdot M>\frac{(n-n^*)}{n}\cdot M,$

As $\frac{(n-n^*)}{n}$ tends to 1 when $n$ tends to infinity, there will be some $N$ such that if $n>N$, $\frac{(n-n^*)}{n}>\frac{M-1}{M}$. Thus $\frac{a_1+a_2+...+a_N}{N}>\frac{N-n^*}{N}M>M-1$. As you can do this for all $M$, the result follows.


答:
The idea in general is kind of ok, but it is not clear enough. You don't want to choose $M^*$, it should be given to you. What you can do is to notice  that from
$$
\frac{a_1+\cdots+a_n}n\geq S_n+ M-\frac{n^*}n\,M,
$$
you obtain

$$
\liminf_{n\to\infty}\frac{a_1+\cdots+a_n}n\geq \liminf_{n\to\infty}S_n+ M-\frac{n^*}n\,M=M.
$$
As you can do this for $M>0$,
$$
\liminf_{n\to\infty}\frac{a_1+\cdots+a_n}n=\infty
$$
and so
$$
\lim_{n\to\infty}\frac{a_1+\cdots+a_n}n=\infty.
$$

Title: Prove that if $\lim_{n\to+\infty} a_n = +\infty$ then $\lim_{n\to+\infty} \frac{a_1+a_2+...+a_n}{n} = +\infty$

Body:
I have to prove a problem, I arrived to a solution but I don't know it is correct.

The problem:

Prove that if
$$\lim_{x\to+\infty} a_n = +\infty$$

Then

$$\lim_{n\to+\infty} \frac{a_1+a_2+...+a_n}{n} = +\infty$$

I thought about doing this similarly to how you prove Ernesto Cesaro's theorem.

By definition

$$\forall M\gt0 \quad \exists n^*: \forall n \gt n^* \quad a_n > M $$

Now I have

$$\frac{a_1+a_2+...+a_{n^*-1}+a_{n^*}+...+a_n}{n}$$

The first part of the fraction can be replaced with

$$S=\frac{a_1+a_2+...+a_{n^*-1}}{n}$$

And then I have all the terms next to $a_{n^*}$ greater than $M$

$$\frac{a_{n^*}+...+a_n}{n} \gt \frac{(n-n^*)M}{n} $$

$$\frac{a_1+a_2+...+a_{n^*-1}+a_{n^*}+...+a_n}{n}\gt S+\frac{(n-n^*)M}{n}$$

Then I choose $M^*$

$$M^*=S+\frac{(n-n^*)M}{n}$$

I have at the end that

$$\frac{a_1+a_2+...+a_n}{n} \gt M^*$$

You can choose whatever $M$ you want, so the problem is proved.

I don't really know if the proof is rigorous, I tried to use that path and I hope that there could be at least something decent in there.

In the case the proof is not valid, I ask you if you can give some tip on where to start to prove it.


问:
Show with a counterexample that $A\nsubseteq A^A$
Definition

A set $R$ is a (binary) relation if any its element is a ordered pair, that is $z\in R$ if and only if there exist $x$ and $y$ such that $z=(x,y)$. In particular if $R$ is contained in the cartesian product of two set $A$ and $B$ we say that $R$ is a relation of between $A$ and $B$ and if $B$ is equal to $A$ we say that $R$ is a relation in $A$.

Definition

If $R$ is a relation we call domain of $R$ that set whose elements are a first coordinate of some pair of the relation, that is
$$
\text{dom}\,R:=\{x:\exists\,y\,\text{such that}\,(x,y)\in R\}
$$
and analogously the range of $R$ is that set whose elements are the second coordinate of the relation, that is
$$
\text{rank}\,R:=\{y:\exists\,x\,\text{such that}\,(x,y)\in R\}
$$

So it is possible to prove that the above two defined set exist using the $ZFC$'s formalism but this now has not matter so we proceed to give the following well know definition.

Definition

A function $f$ is a relation such that if $(x,y)$ and $(x,z)$ are such that $(x,y),(x,z)\in f$ then $y=z$.

Definition

Let $A$ and $B$ sets. So the set whose element are functions from $A$ to $B$ is denoted by the symbol $B^A$.

Again it is possible to prove that the above defined set exist using $ZFC$'s formalism but now this again has not matter.

So by the previous things I thought that any element $a$ of a (not empty) set $A$ could be regarded as a costant function so that I ask to me if $A$ is a subset of $A^A$ but this seems to me very stranger and so I would like to know the opinon of anyone with more competences of mine. In particular I have observed that if $a\in A^A\cap A$ then $a\subseteq A\times A$ and so either $a=\emptyset$ either there exist $c,d\in A$ such that $a=(c,d)\in\{\{c\},\{c,d\}\}$ but by this I did not deduce any contradiction. So could someone help me, please?

答: Each element $a\in A$ can be identified with the constant function $f_a:A\rightarrow A:x\mapsto a$. In this way, $a$ can be thought as an element of $ A^A$.


问:
Is every subgroup of $\mathrm{Isom}(\mathbb{R}^n)$ a semidirect product $T \rtimes Q$?
It is well known that the group of isometries of Euclidean space $\mathrm{Isom}(\mathbb{R}^n)$ splits as the semidirect product $\mathbb{R}^n \rtimes O(n)$. However, is it also true that every subgroup $G \le \mathrm{Isom}(\mathbb{R}^n)$ is isomorphic to the semidirect product $T \rtimes Q$, where $T = G \cap \mathbb{R}^n$ (this is a slight abuse of notation) and $Q$ is the projection of $G$ onto $O(n)$?

My initial instinct is that this is false. Indeed, suppose that we have a subgroup $G$ satisfying the condition that: for every $\psi \in G$, $\psi(x) = Ax + b$, where $A \in O(n)$ and $b \in \mathbb{R}^n$, if $A$ is not the identity, then $b \ne 0$. That is, in $G$ there are no isometries of the form $x \mapsto Ax$ where $A$ is not the identity. Suppose further that $G$ is not comprised solely of translations. Then $G$ cannot be isomorphic to the semidirect product, because $\{0\} \times Q \ne \{0\} \times \{I\}$ is a subgroup of $T \rtimes Q$. To be explicit, no map $\phi : T \rtimes Q \rightarrow G$ can be injective, since $G$ is in bijective correspondence with the proper subset $G' \subsetneq T \rtimes Q$ where $G' = \{(b,A) \in T \rtimes Q \, | \,\exists \psi \in G, \psi(x)=Ax+b\}$.

The only problem with this approach is that it assumes the existence of such a $G$, and thus far I have failed to produce an example. I would very much appreciate some help with this. Am I wrong; does the result in fact hold? Otherwise, is there a better way to prove its falsity? I feel like there must be a better way to do this.

答:
This is not a proper answer but a proposal for where to potentially find simple counter examples.

Consider a one parameter subgroup $\gamma:\Bbb{R}\to\mathrm{Isom}(\Bbb{R}^2)$ that

actually rotates (e.g. $p(\gamma(t))$ is the rotation of angle $t$) and

actually translates ($\gamma(2\pi)$ is a non-identity translation).

I expect under these circumstances $\gamma$ induces a homeomorphism onto its image. In any case, the image $G=\gamma(\Bbb{R})$ is connected.

The translations in the image, i.e. $T=G\cap\Bbb{R}^2$, form a discrete group and the projection $Q$ of $G$ is $\mathrm{SO}(2)$. Whatever semi-direct product structure you would consider involving $T$ and $Q$ it would produce group with infinitely many connected components and couldn't be isomorphic to the connected group $G$.

I imagine it should be easier to do in $\Bbb{R}^3$ taking something like $$\gamma(t)\big(V\big)=R_t V + te_z$$ where $R_t$ is the rotation of angle $t$ around the axis $Oe_z$.


问:
dual form of perceptron
I'm trying to frame the perceptron in terms of familiar optimization concepts but haven't found a nice explanation of the perceptron's dual form.

We can phrase the primal problem as
\begin{equation}
\begin{aligned}
& \underset{w \in \mathbb{R}^d}{\text{minimize}}
&& J(w) = \frac{1}{N}\sum_{i=1}^N l(w,x_i) = \frac{1}{N}\sum_{i=1}^N -y_i \times [w \cdot x_i]_+
 \\
\end{aligned}
\end{equation}
for $S = \{(x_i, y_i)\}_{i=1}^N$ with $x_i \in \mathbb{R}^d$, $y_i \in \{\pm 1\}$ and $[a]_+ = \max\{a,0\}$. Note that $l(w,x)$ is the hinge loss, a convex relaxation of the $0/1$ loss.

To minimize $J(w)$, we can use (sub)gradient descent. For $y_i \times w\cdot x_i < 0$ (we've made an error), we have a nonzero (negative) gradient. For $y_i \times w \cdot x_i > 0$ (we've correctly classified), we have a zero gradient. At the kink (i.e., when $w \cdot x_i=0)$ we can choose any subgradient between zero and $-y_i x_i$. In particular, we can use
$$
\partial_wJ(w) =  -(y_i \, x_i)\, \mathbb{1}\{y_i \times (w \cdot x_i) \leq 0\}
$$
and the subgradient descent update $w^{(t+1)} = w^{(t)} - \partial_wJ(w)$ to recover the standard perceptron rule (note that the standard perceptron rule is subgradient descent with a fixed step size).

However, we might want to introduce nonlinearity into our model to make it more expressive. If we can write $J(w)$ only involving inner products of the $x_i$s, then we can use the "kernel trick" to map the $x_i$s to a richer space (a RKHS) space. To do so, we first consider the "dual" form of the problem.

Various sets of notes say that we can express $w \in \mathbb{R}^d$ as a sum of the training examples, i.e., $w = \sum_{i=1}^N \alpha_i y_i x_i$, but none are explicit about why; they just list the update procedure for the "dual" form.

I guess we can see that initializing $w^{(0)} = 0$, gradient descent a gives linear combinations of the training examples, but this isn't satisfying. I feel that the Representer theorem is at play somehow, but I don't see the RKHS.

So, what's the dual problem to $\min_w J(w)$? Naively taking the dual of $\min_w J(w)$ doesn't give anything interesting, so I feel that there must be some constraint or reformulation that gives the meaningful dual update procedure. How can we see this?

答:
We can derive the dual form by using the Lagrange duality. Briefly, we first formulate the objective function and the constraints of the perceptron, and use that to solve the generalized Lagrangian. Then, via KKT stationary and complementary conditions, we can express $w$ as a linear combination of the training samples $w = \sum_{i=1}^{n} \alpha_i y_i \vec{x_i}$.

For the full derivation and explanation, please see my answer to a similar question here.

Title: dual form of perceptron


答: When I see $b_nb_{n+2}=b_{n+1}^2-1$, or equivalently $c_nc_{n+2}=c_{n+1}^2-q^2$ with $c_n:=qb_n$, I immediately think of$$\sin(nx)\sin((n+2)x)=\tfrac{\cos(2x)-\cos((2n+2)x)}{2}=\sin^2((n+1)x)-\sin^2x,$$with $q=\sin x$. So some $x$ gives $b_n=\tfrac{\sin nx}{\sin x}$. Since $b_2=k$, $k=2\cos x$.

Title: BMO2 2020 Question 4

Body:
So I attempted the 2020 paper for BMO2 (https://bmos.ukmt.org.uk/home/bmo2-2020.pdf), but I've been stuck on Q4.

A sequence $b_1,b_2,b_3,...$ of non-zero real numbers has the property that $b_{n+2}=\frac{b^2_{n+1}−1}{b_n}$ for all positive integers n. Suppose that $b_1=1$ and $b_2=k$ where $1<k<2$. Show that there is some constant $B$,depending on $k$, such that $−B≤b_n≤B$ for all $n$. Also show that, for some $1<k<2$, there is a value of $n$ such that $b_n>2020$.

The only idea that came to mind was to try and solve for an nth term (which I could not do) or to use induction to prove the existence of bounds, which doesn't seem to work out since we have the division.

Looking online I found someone's solution, in which they gave the nth term as
$$ b_n = \frac{\sin(n\gamma)}{\sin(\gamma)} $$
where $\gamma = \arccos(k/2)$
And from here it's trivial.

However they did not say how they derived this formula apart from "intuition". The only intuitive link I see between the nth term and the recurrence is that both feel "bouncy".

The only method I can think of that would be helpful here is generating functions, but as far as I'm aware they cannot help when we have products of sequences except for the special case of convolutions and convolutions multiplied by binomial coefficients.

So my questions are:

How could you derive this nth term?

Does this fit into a larger pattern of recurrence relations that can be solved using slightly "squished" trig function?

How could this be solved using only elementary mathematics? (As the competition is intended so every question can, at least in theory, be done using clever tricks without higher maths (given that the question did not ask for an nth term, I presume there is a method to solve this that does not actually require finding one)


问:
Pullback Calculation
If we define the 2-form $\omega=\frac{1}{r^3}(x_1dx_2\wedge dx_3+x_2dx_3\wedge dx_1+x_3dx_1\wedge dx_2)$ with $r=\sqrt{x_1^2+x_2^2+x_3^2}$

If we now define $x(\theta,\phi)=(\sin\theta\cos\phi,\sin\theta\sin\phi,\cos\theta)$ for $\theta\in(0,\pi)$ and $\phi\in (0,2\pi)$

I now want to show that the pullback of this map is:

$x^*\omega=\sin\theta d\theta\wedge d\phi$

Now my definition of the pullback of a map $c:[a,b]\rightarrow D$ is $\alpha(c'(t))dt$ but am unsure as to how to proceed? I can see that this curve $x$ is a parametrization of the sphere in $\mathbb{R}^3$ but after that I am a bit lost?

Thanks for any help

答:
A more general equation for how to compute pullbacks is as follows: If $f: M \to N$ is a smooth map of smooth manifolds and $\omega$ is an $n$-form on $N$, written in local coordinates as
$$ \omega = \sum_I \omega_I dy^{i_1} \wedge \cdots \wedge dy^{i_n}$$
then $f^*\omega$ can be written in induced coordinates as
$$ f^*\omega = \sum_I (\omega_I \circ f) d(y^{i_1} \circ f) \wedge \cdots \wedge d(y^{i_n} \circ f)$$
where you think of $y^i$ as the function which picks out the $i^{th}$ coordinate of $f$.

Your $\omega$ is given by
$$ \omega = \omega_{23} dx_2 \wedge dx_3 + \omega_{31} dx_3 \wedge dx_1 + \omega_{12} dx_1 \wedge dx_2$$
where $\omega_{23} = \frac{x_1}{r^3}, \omega_{31} = \frac{x_2}{r^3}$ andd $\omega_{12} = \frac{x_3}{r^3}$. So now you just use the formula: I will do the $\omega_{23} dx_2 \wedge dx_3$ term as an example:

$$ f^*(\omega_{23} dx_2 \wedge dx_3) = (\omega_{23} \circ f) d(x_2 \circ f) \wedge d(x_3 \circ f) $$

Now
\begin{align*}
\omega_{23} \circ f &= \frac{\sin\theta \cos\phi}{\sqrt{\sin^2\theta\cos^2\phi + \sin^2\theta \sin^2\phi + \cos^2\theta}^3} = \sin\theta\cos\phi \\
d(x_2\circ f) &= d(\sin\theta\sin\phi) = \cos\theta \sin\phi d\theta + \sin\theta \cos\phi d\phi \\
d(x_3\circ f) &= d(\cos\theta) = -\sin\theta d\theta.
\end{align*}
Putting it all together, we get
\begin{align*}
(\omega_{23} \circ f) d(x_2 \circ f) \wedge d(x_3 \circ f) &= (\sin\theta\cos\phi)(\cos\theta\sin\phi d\theta + \sin\theta\cos\phi d\phi) \wedge (-\sin\theta d\theta ) \\
&= \sin^3\theta\cos^2\phi d\theta \wedge d\phi
\end{align*}

(Of course, modulo mistakes in my computations!)

Title: Pullback Calculation


问:
Proof that a graphic sequence realizes a specific graph structure
I have a problem understanding not only this proof, but also the theorem.

Definition:   A non-increasing sequence $\langle d_{1}, d_{2}, ..., d_{n} \rangle$ is said to be graphic if it is the degree sequence of some simple graph.

Theorem: Let $\langle d_{1}, d_{2}, ..., d_{n} \rangle$ be a graphic sequence, with $d_{1} \geqslant d_{2} \geqslant ... \geqslant d_{n}$. Then there is a simple graph with $\{v_{1}, v_{2}, ..., v_{n}\}$ as a vertex-set satisfying $deg(v_{i}) = d_{i}$ for $i = 1, 2, ..., n$, such that $v_{1}$ is adjacent to vertices $v_{2}, ..., v_{d_{1} + 1}$.

I don't understand the last part of the theorem. Does this mean that the vertex with the highest degree (for example 5) is adjacent to the next 5 vertexes with the highest degrees in the sequence (for example 4, 3, 2, 2, 1, but not 2, 2, 2, 2, 1)?

Proof:

Among all simple graphs with $\{v_{1}, v_{2}, ..., v_{n}\}$ as a vertex-set and $deg(v_{i}) = d_{i}, i = 1, 2, ..., n$, let $G$ be one for which $r = | N_{G}(v_{1}) \cap \{v_{2}, ..., v_{d_{1} + 1}\}|$ is maximum [1].

If $r = d_{1}$, then the conlusion follows. If $r < d_{1}$, then there exists a vertex $v_{s}$, where $2 \leqslant s \leqslant d_{1} + 1$, such that $v_{1}$ is not adjacent to $v_{s}$, and there exists a vertex $v_{t}$, where $t > d_{1} + 1$ such that $v_{1}$ is adjacent to $v_{t}$, since $deg(v_{1}) = d_{1}$ [2].

Moreover, since $deg(v_{s}) \geqslant deg(v_{t})$, there exists a vertex $v_{k}$ such that $v_{k}$ is adjacent to $v_{s}$ but not to $v_{t}$. Let $\tilde{G}$ be the graph obtained from $G$ by replacing the edges $\{v_{1}, v_{t}\}$ and $\{v_{s}, v_{k}\}$ with the edges $\{v_{1}, v_{s}\}$ and $\{v_{t}, v_{k}\}$. Then the degrees are all preserved and $v_{s} \in N_{\tilde{G}}(v_{1}) \cap \{v_{3}, ..., v_{d_{1} + 1}\}$.

Thus, $|N_{\tilde{G}}(v_{1}) \cap \{v_{2}, ..., v_{d_{1} + 1}\}| = r + 1$, which contradicts the choice of $G$ and completes the proof [3].

Questions:
[1]: What does that mean exactly, in simple words? Does that mean that it is a graph, where the vertex with the highest degree is connected to other vertices with highest degrees? This is the same problem that I have with the theorem I guess.

[2]: Why does $v_{t}$ have to have $t > d_{1} + 1$ and why does it have to be adjacent to $v_{1}$?

[3]: I am not sure I understand the last step. However, I think that it would make sense once I understand the previous ones.

Thank you for the clarifications.

答:
Yes, the goal is to get a graph where the highest-degree vertex $v_1$ is adjacent to the $d_1$ next-highest degree vertices.

This has no purpose of its own, but it's important because this is the one thing we know we can always guarantee. The degree sequence $d_1, \dots, d_n$ might have many realizations, and $v_1$ might have different sets of neighbors in them, and we don't know exactly which sets of neighbors are possible. However, we know that the set $\{v_2, \dots, v_{d_1+1}\}$ must be possible.

Later on, this gives us an effective algorithm for checking if a degree sequence is graphic.

The intuitive idea in the proof is that we can start with any graph with this degree sequence, and perform edge swaps (replacing edges $uv$ and $xy$ with edges $ux$ and $vy$) until it has the form required by the theorem.

How can we know we are making progress in the right direction? Well, we can measure "how good" a graph is for our purposes by seeing how many edges $v_1$ has to the vertices in $S = \{v_2, v_3, \dots, v_{d_1+1}\}$. Eventually, we'd like the answer to be "$d$: all of them". We can make sure that we're making progress towards that by proving the following lemma.

Lemma. If $v_1$ is not adjacent to all of the vertices in $S$, then we can perform an edge swap to increase the number of neighbors $v_1$ has in $S$.

Proof. This is what's going on in the second and third paragraphs of your proof. Let me explain more clearly where $v_s, v_t, v_d$ come from.

If $v_1$ is not adjacent to all the vertices in $S$, then there must be some vertex in $S$ that it isn't adjacent to: that's $v_s$.

In total, $v_1$ must have $d_1$ neighbors. There are $d_1$ vertices in $S$, but $v_1$ isn't adjacent to all of them. So $v_1$ needs a neighbor outside $S$ to get to $d_1$ neighbors: that's $v_t$.

Since $\{v_1\} \cup S$ has all the highest-degree vertices, we have $\deg(v_s) \ge \deg(v_t)$. Moreover, $v_t$ is at a disadvantage: it is adjacent to $v_1$, but $v_s$ isn't. To make up for that, there must be at least one vertex adjacent to $v_s$ but not $v_t$: that's $v_k$.

At this point, we do what your proof does: delete $v_1v_t$ and $v_s v_k$, then add $v_1 v_s$ and $v_t v_k$. (All this work was to make sure that edges $v_1 v_s$ and $v_t v_k$ don't yet exist.) Now $v_1$ has one more neighbor in $S$: the vertex $v_s$.

Now I can explain why we say "Let $G$ be the graph for which $|N(v_1) \cap S|$ is maximum".

This is something called the extremal principle. It's a shortcut for proof-writing. We have a lemma that says: if $N(v_1) \ne S$, it's possible to change the graph to make $|N(v_1) \cap S|$ larger. Intuitively, what we want to say is "apply this lemma until you can't apply it anymore", but that sounds vague.

So instead, we pick the graph $G$ with the largest possible value of $|N(v_1) \cap S|$, because then we know that the value of $|N(v_1) \cap S|$ can't be increased any further. The lemma says "it can always be increased further, with one exception: if $N(v_1) = S$". So we conclude that $G$ has $N(v_1) = S$.


问:
Prove $f :\mathbb{R} \to \mathbb{R}$ is continuous iff for every open set $U \subset \mathbb{R}$, the preimage is open.
I am trying to prove that a function $f :\mathbb{R} \to \mathbb{R}$ is continuous iff for every open set $U \subset \mathbb{R}$, the preimage $f^{-1}(U) = \{x\in\mathbb{R}|f(x)\in U\}$ is open.

To prove the backwards implication I have that$$\forall x\in f^{-1}(U), \exists\delta>0, (x-\delta,x+\delta)\subset f^{-1}(U)$$^ from the definition of an open set. $$(x-\delta,x+\delta)\subset f^{-1}(U)$$ and then applying $f$ $$(f(x+\delta),f(x-\delta))\subset U$$

So $f$ hits all the points in that interval, can I then say it is continuous over that interval? Or is my method of proof completely wrong.

答:
Suppose the set $f^{-1}(U)=\{x\in\mathbb{R}:f(x)\in U\}$ is an open set. We want to see that $f$ is a continuous function, that is, for all $\varepsilon>0$ and $a\in\mathbb{R}$ there exists $\delta>0$ such that $|x-a|<\delta$ implies that $|f(x)-f(a)|<\varepsilon$.

Let $a\in\mathbb{R}$ and $\varepsilon>0$. Consider the set $U_{\varepsilon}=(f(a)-\varepsilon,f(a)+\varepsilon)$, which is open. Then $f^{-1}(U_{\varepsilon})=\{x\in\mathbb{R}:f(x)\in(f(a)-\varepsilon,f(a)+\varepsilon)\}$ is open on $\mathbb{R}$. Notice that $a\in f^{-1}(U_{\varepsilon})$. Thus, there exists $\delta$ such that $(a-\delta,a+\delta)\subset f^{-1}(U_{\varepsilon})$.

If $x\in (a-\delta,a+\delta)$ then $|x-a|<\delta$. Also, this implies that $x\in f^{-1}(U_{\varepsilon})$, which means that $f(x)\in(f(a)-\varepsilon,f(a)+\varepsilon)$; rewriting, $|f(x)-f(a)|<\varepsilon$. Therefore $f$ is continuous.


问:
Verification of a limit with a doubtful result
I tried to check this limit with the definition :

$$\lim_{x\to +\infty}\sqrt{x^2+1}=+\infty$$

I have studied that in order to verify this type of limit I have to solve the inequality:

```<code>f(x)> M
</code>```

with Where M is a very large value decided by our choice.

So I had to solve:

$$\sqrt{x^2+1} >M$$

The result is this, but I'm not sure it's right. I should obtain, by solving the associated inequality, an unlimited interval above, but in the result I obtain both an unlimited interval above and an unlimited interval below.

Here is the result:

$$ x < - \sqrt{m^2-1} ,\quad x> + \sqrt{m^2-1}$$

答:
You are overlooking a few things:

Since you are taking the limit as $x \to +\infty$, you only need to be concerned about values of $x$ where $x > 0.$

There is a convention that for any non-negative $y, \sqrt{y}$ automatically refers to the non-negative square root.

Besides the above considerations, the result that you want is actually an indirect result of the squeeze theorem.

The idea is that from the initial points in this answer, either the limit goes to $+\infty$, or there is an upper bound on $\sqrt{x^2+1}$, as $x \to +\infty$.  However, since $\sqrt{x^2 + 1}$ is strictly increasing as (non-negative) $x$ increases, the assumption that there is an upper bound on $\sqrt{x^2 + 1}$ implies that $\sqrt{x^2 + 1}$ must converge to some non-negative value $L$.  Assume the latter, and apply the squeeze theorem to obtain a contradiction.

That is, for all non-negative $x$, $x = \sqrt{x^2} < \sqrt{x^2 + 1}.$  Therefore, if there is a finite $L$ that represents the limit of $\sqrt{x^2 + 1}$, then you would immediately know, from the squeeze theorem, that as $x \to \infty, \sqrt{x^2}$ can not go to infinity.

Since $x = \sqrt{x^2}$, this is an immediate contradiction.


问:
Checking if the complement of an undirected graph is bipartite
Is there any linear time algorithm that says if the complement of a given undirected graph is bipartite?

I've tried using König's theorem, with no success.

答:
There is a trick to that problem : if the graph has $n$ nodes and $m$ edges, then the solution is an algorithm in $O(n^2)$, but this would be linear in the input graph's size because $m = \Theta(n^2)$.

The key idea is : if a graph is bipartite, then its complement is dense (it has more than $\frac{n^2}{4} - \varepsilon n$ edges). Indeed, the bipartite graph is a subgraph of the complete bipartite graph $K_{m,n}$ which has $mn$ edges for $(m+n)$ vertices, which (for any ratio of $m$ and $n$) has a density inferior to $\frac 1 2$ (asymptotically), so the complement of any bipartite graph has a density of at least $\frac 1 2$ (also asymptotically)

Then, the algorithm deciding "given the graph $G = (V,E)$, decide whether $G^C = (V, V^2 \setminus E)$ is bipartite" goes as follow :

If $|E| < \frac {|V|^2} 4$, then answer "No"

Else, compute $G^C$ explicitly, and apply the classical algorithm for the detection of bipartite graphs. That algorithm is linear in $|V| + |V^2 \setminus E| = O(|V|^2) = O(|E|)$ so is linear in the input graph's size.

(of course, the bound for answering "No" isn't exactly $\frac {|V|^2} 4$, but the exact optimal value might be annoying to compute)


答:
Formally, it is false that $A \subseteq A^A$ for a generic set $A$. Take for instance $A = \{*\}$. Then, $A^A = \{\{(*,*)\}\}$ (i.e. the only function in $A^A$ is the identity on $A$), so $* \in A$ but $* \notin A^A$, thus $A \not\subseteq A^A$. Actually, $A$ and $A^A$ are disjoint in this case.

However, there is a canonical injection of $A$ into $A^A$, the one correctly defined by Wuestenfux in his answer:

Each element $a \in A$ can be identified with the constant function
\begin{align}
f_a \colon& \, A \to A
\\
&\,\,x \mapsto a
\end{align}

In this way, each element $a \in A$ can be thought as an element of $A^A$. Therefore, "morally" (but not formally) $A \subseteq A^A$.

Note that there is an error in your argument. If you assume $a \in A^A \cap A$, then $a \subseteq A \times A$, but possibly there is no $a \in A^A \cap A$ and you are assuming something impossible. Indeed, from $a \in A^A \cap A$ it follows that $a \in A^A$ (and hence $a \subseteq A \times A$) and $a \in A$, but we have just seen that this can be impossible, for instance when $A = \{*\}$ and so $A^A \cap A = \emptyset$.

Title: Show with a counterexample that $A\nsubseteq A^A$

Body:
Definition

A set $R$ is a (binary) relation if any its element is a ordered pair, that is $z\in R$ if and only if there exist $x$ and $y$ such that $z=(x,y)$. In particular if $R$ is contained in the cartesian product of two set $A$ and $B$ we say that $R$ is a relation of between $A$ and $B$ and if $B$ is equal to $A$ we say that $R$ is a relation in $A$.

Definition

If $R$ is a relation we call domain of $R$ that set whose elements are a first coordinate of some pair of the relation, that is
$$
\text{dom}\,R:=\{x:\exists\,y\,\text{such that}\,(x,y)\in R\}
$$
and analogously the range of $R$ is that set whose elements are the second coordinate of the relation, that is
$$
\text{rank}\,R:=\{y:\exists\,x\,\text{such that}\,(x,y)\in R\}
$$

So it is possible to prove that the above two defined set exist using the $ZFC$'s formalism but this now has not matter so we proceed to give the following well know definition.

Definition

A function $f$ is a relation such that if $(x,y)$ and $(x,z)$ are such that $(x,y),(x,z)\in f$ then $y=z$.

Definition

Let $A$ and $B$ sets. So the set whose element are functions from $A$ to $B$ is denoted by the symbol $B^A$.

Again it is possible to prove that the above defined set exist using $ZFC$'s formalism but now this again has not matter.

So by the previous things I thought that any element $a$ of a (not empty) set $A$ could be regarded as a costant function so that I ask to me if $A$ is a subset of $A^A$ but this seems to me very stranger and so I would like to know the opinon of anyone with more competences of mine. In particular I have observed that if $a\in A^A\cap A$ then $a\subseteq A\times A$ and so either $a=\emptyset$ either there exist $c,d\in A$ such that $a=(c,d)\in\{\{c\},\{c,d\}\}$ but by this I did not deduce any contradiction. So could someone help me, please?


问:
a flatness criterion
I'm having trouble with part (b) of Exercise 10.5.25 from Dummit & Foote (the goal of the problem is to prove that $A$ is a flat $R$-module iff $A\otimes_R I\to A\otimes_R R$ is one-to-one for all finitely-generated ideals $I$ of $R$).

Part (b) has 3 parts. The first and third I've done, but I'm stuck on the second. Here're the first two parts of (b):

If $A\otimes_R I\to A\otimes_R R$ is injective for every finitely-generated ideal $I$, prove that $A\otimes_R I\to A\otimes_R R$ is injective for every ideal $I$. Show that if $K$ is any submodule of a finitely generated free module $F$, then $A\otimes_R K\to A\otimes_R F$ is injective.

Here's what I've tried:

Let $e_1,\ldots,e_n$ be a basis for $F$. Let $x\in \ker(1\otimes\iota)$, where $\iota\colon K\to F$ is inclusion. Then
$$x=\sum_{i=1}^m a_i\otimes k_i$$
for some $a_i\in A$, $k_i\in K$. Express each $k_i$ in terms of the basis: $k_i=\sum_j r_{ij}e_j$. Then
$$0 = 1\otimes \iota(x)=\sum_i\sum_j a_i\otimes r_{ij}e_j=\sum_j\left(\sum_i a_i r_{ij}\right)\otimes e_j.$$
So, using the fact that $A\otimes_R F\cong A^n$ via $\sum_j b_j\otimes e_j \mapsto (b_1,\ldots,b_j)$, we get
$$\sum_i a_i r_{ij}=0$$
for all $j$. My issue is that I don't know how to lift this back to $A\otimes_R K$. Also, I think I should be using the first part of (b) somewhere.

Any hints? Am I even on the right track?

答:
First note that that the condition $A \otimes_R K \to A \otimes_R F$ is injective for all free $R$-modules $F$ and submodules $K$ is equivalent to $A$ being flat.  So you will definitely need to assume that $A \otimes_R I \to A \otimes_R R$ is injective for all ideals $I \subseteq R$.

We will prove that $\operatorname{Tor}_1^R(A, F/K) = 0$ for any such $F$ and $K$ and this will give you injectivity of the map using the long exact sequence coming from Tor.  You're going to do this by induction on the rank of $F$.  When $F$ has rank $1$ it's simply $R$ and $K$ is some ideal $I$.  Look at the exact sequence $I \to R \to R/I$.  Write down the corresponding long exact sequence for $\operatorname{Tor}_1^R(A, -)$.  Use injectivity of $A \otimes_R I \to A \otimes_R R$ and that $R$ is free to get $\operatorname{Tor}_1^R(A, R/I) = 0$.

Next the inductive step.  Let $e_1, \ldots, e_n$ be a basis for $F$.  Let $N = \langle e_1, \ldots, e_{n-1}\rangle$ and consider the exact sequence
$$\frac{N}{N \cap K} \to F/K \to \frac{F/N}{(K + N)/N}$$
Both $N$ and $F/N$ are free of smaller rank.  So use the inductive hypothesis along with the long exact sequence of $\operatorname{Tor}_1^R(A, -)$ again to get that $\operatorname{Tor}_1^R(A, F/K) = 0$.

Title: a flatness criterion


问:
A slight twist to Folland 1.4.18 b)

18. Let $\mathcal{A}\subset\mathcal{P}(X)$ be an algebra, $\mathcal{A}_\sigma$ the collection of countable unions of sets in $\mathcal{A}$, and $\mathcal{A}_{\sigma\delta}$ the collection of countable intersections of sets inf $\mathcal{A}_\sigma$. Let $\mu_0$ be a premeasure on $\mathcal{A}$ and $\mu^*$ the induces outer measure.

a. For any $E\subset X$ and $\epsilon>0$ there exists $A\in\mathcal{A}_\sigma$ with $E\subset A$ and $\mu^*(A)\leq\mu^*(E)+\epsilon$.

b. If $\mu^*(E)<\infty$, then $E$ is $\mu^*$-measurable iff there exists $B\in\mathcal{A}_{\sigma\delta}$ with $E\subset B$ and $\mu^*(B\setminus E)=0$.

c. If $\mu_0$ is $\sigma$-finite, the restriction $\mu^*(E)<\infty$ in (b) is superfluous.

Now there is a slight twist to part b).

Let $\mu^*(E) < \infty$, then I want to show that $E$ is $\mu^*$-measurable iff there exists $\mathcal{A}_{\sigma \delta}$ and $C \in \mathcal{A}_{\delta \sigma }$ with $ C \subset E \subset B$ such that $\mu^*(B / C)=0$.

I've proven part b). But for the forward direction, I'm not sure how to construct such $C \in \mathcal{A}_{\delta \sigma }$.

I thought about using the fact that we have $\mathcal{A}_{\delta \sigma } \subset M(\mathcal{A}) \subset M^*$, where $ M(\mathcal{A})$ is the $\sigma$-algebra generated by $\mathcal{A}$, and $M^*$(a $\sigma$-algebra) is the set of $\mu^* $-measurable sets.

But that didn't me get anywhere.

Thanks in advance!

答:
You have already proven that:

b. If $\mu^*(E)<\infty$, then $E$ is $\mu^*$-measurable iff there exists $B\in\mathcal{A}_{\sigma\delta}$ with $E\subset B$ and $\mu^*(B\setminus E)=0$.

Now, if $\mu^*(E)<\infty$  and $E$ is $\mu^*$-measurable, take $B\in\mathcal{A}_{\sigma\delta}$ with $E\subset B$ and $\mu^*(B\setminus E)=0$.

Since  $\mu^*(E)<\infty$, there is $B_1\in\mathcal{A}_{\sigma}$ with $E\subset B_1$ and $\mu^*(E) \leqslant \mu^*(B_1) \leqslant \mu^*(E)+1$.

Consider $B_1 \setminus E$. It is easy to see that $\mu^*(B_1 \setminus E)<\infty$ and $B_1 \setminus E$ is $\mu^*$-measurable. So applying item b again we have, that there is $D\in\mathcal{A}_{\sigma\delta}$ with $B_1 \setminus  E\subset D$ and $\mu^*(D\setminus (B_1 \setminus E))=0$. Note that
$$ D\setminus (B_1 \setminus E)=D \cap (B_1 \cap E^c)^c= (D\cap B_1^{\phantom{1}c})\cup (D\cap E) $$
So, from  $\mu^*(D\setminus (B_1 \setminus E))=0$, we can conclude that  $\mu^*(D\cap E)=0$.

Take $C = E \setminus D$. Since $B_1 \setminus  E\subset D$, we have that $C= E \setminus D= B_1 \setminus D$. It is immediate that $C \in \mathcal{A}_{\delta \sigma }$ and  $ C \subset E$. So, we have $ C \subset E \subset B$ and

$$B\setminus C= (B\setminus E)\cup (E\setminus C)=(B\setminus E)\cup (E\setminus (E \setminus D))= (B\setminus E) \cup (E\cap D) $$
So
$$ \mu^*(B\setminus C)\leqslant \mu^*(B\setminus E)+ \mu^*(E\cap D)=0+0=0$$

Title: A slight twist to Folland 1.4.18 b)