问:
Describing a graph property through logical operations

Let $G$ be a finite, undirected graph (with no parallel edges or self-loops) with $|V(G)| \geq 1$. A $k$-factor  $H$ of $G$ is a spanning subgraph of $G$ (with $V(H) = V(G)$) in which every vertex has degree $k$.

Construct a formula $\phi_G$ that is exactly satisfiable when $G$ has a $2$-factor. Describe how we can construct a $2$-factor for $G$ from every interpretation (model) that satisfies $\phi_G$ and how we can construct a model satisfying $\phi_G$ from every $2$-factor for $G$.

What I'm trying to do is describe this $2$-factor property in terms of big conjunctions and disjunctions. For that, I need to define variables and connect them using these conjunctions and disjunctions while imposing the necessary restrictions to obtain a meaningful $\phi_G$. I'm failing at this miserably.

What should the variables stand for and would we begin to construct the formula? I thought about describing the $2$-factor property in predicate logic and then translating it into propositional logic, but I didn't get far there either.

What I do know is that a $1$-factor is just a perfect matching. So if we could somehow obtain a formula for that, the $2$-factor should have a similar structure, but I'm really not sure how to do this or if this the right approach.

Any help would be much appreciated.

EDIT: @HallaSurvivor: Sorry if I'm making this too complicated, but consider this graph:

For vertex $1$, if we had chosen the edge $\{1, 2\}$, then we wouldn't have a $2$-factor, since the cycles aren't disjoint anymore. So how could we know which edges to use from "looking at the graph"? Most of the time (actually always) we don't know what the graph looks like or if it's even connected. For a vertex $x$, the set of all adjacent edges is $\{e_i | x \in e_i \}$. From these edges/variables, we need to find $e_i, e_j$ with $i \neq j$ and set them to true, this would be our $\phi_x$. I'm not sure how to do this. Can you give me a hint or an example for $\phi_x$ for a concrete $x$?

答:
Welcome to MSE!

Hint:

You're looking for a subset of the edges, so you might think of adding a variable $e_i$ for every edge. We want to think of $e_i$ as True whenever we keep it for our 2-factor, and False if we don't. Then every assignment of $e_i$ corresponds to a subgraph, where you keep exactly the edges marked True.

Since you're trying to build a 2-factor, you want to know that every vertex is $2$-regular in the subgraph. So for every vertex $x$, look at its neighbors $\{e_1, \ldots, e_n\}$. You want to write down $\phi_x$ which reads "exactly 2 of $e_1 \ldots e_n$ are True". Can you see how to do that? Importantly we know the graph in advance, so we can "hard code" the $e_i$ that are edges adjacent to $x$.

I then claim that the (finite!) conjunction $\bigwedge_x \phi_x$, is the formula you want. Do you see why?

Edit:

Let's use the graph you showed as an example. I've added labels to the rest of the vertices too.

We'll write $e_{ij}$ for a boolean variable corresponding to an edge connecting $i$ to $j$ (if one exists). Let's always write it with $i < j$ so that we have exactly one variable for every edge.

For example, we will have variables $e_{12}, e_{15}, e_{16}$, but not $e_{13}$, since there is no edge from $1$ to $3$ in the graph.

Now, $\phi_1$ should say "exactly two of the edges touching $1$ are true". We can express this as

$$(e_{12} \land e_{15}) \lor (e_{12} \land e_{16}) \lor (e_{15} \land e_{16})$$

At this point you should stop, and write down $\phi_n$ for all the other $2 \leq n \leq 9$. At least do a few, so that you're convinced you know what's going on.

Ok, now that we have all the $\phi_n$, each of which says "exactly two of my edges are True", we'll conjoin them all:

$$\phi_G = \phi_1 \land \phi_2 \land \ldots \land \phi_9$$

I claim, now, that $\phi_G$ is satisfiable if and only if we can find a $2$-factor in $G$.

Well, we have a $2$-factor in $G$ given to us (it's shown in the picture). If we make the assignment

$$e_{ij} =
\begin{cases}
1 & e_{ij} \text{ is used in the $2$ factor} \\
0 & e_{ij} \text{ is NOT used in the $2$ factor}
\end{cases}
$$

Then I claim this assignment makes $\phi_G$ true. Why? Because in a $2$ factor, any vertex sees exactly 2 edges of the 2 factor. That's what a $2$ factor does.

At this point you should check by hand that the assignment shown in the picture actually does make $\phi_G$ true.

Lastly, we want to say that any assignment of the variables which makes $\phi_G$ true will be a $2$ factor. That is, given some assignment of the $e_{ij}$ to $0$ and $1$ which makes $\phi_G = 1$, we claim

$$ \{ e_{ij} \mid e_{ij} \text{ is assigned $1$} \} \text{ is a $2$ factor}$$

Again, the idea is simple:

Every vertex $n$ must see exactly $2$ edges (since that's what $\phi_n$ says, and we know $\phi_n$ is true). So the edges we keep form a $2$ factor.

Convince yourself of this. Maybe try some small examples by hand. I don't think you'll really understand it until you play with it yourself for a while, so make sure you do!

I hope this helps ^_^


问:
Intersection multiplicity does not go down after restriction to closed subvariety: proof using filtrations
Let $S$ be a noetherian domain, and $f\in S$ neither a unit nor a zero divisor. Let $P$ be a minimal prime over $f$, let $I\subset S$ be a prime ideal, suppose the image of $f$ in $S/I$ is neither a unit nor a zero-divisor, and let $Q$ be a minimal prime over $S/(I+f)$ containing $P$. I'm looking to verify that $\operatorname{length}_{S_P} S_P/(f)\leq \operatorname{length}_{S_Q} S_Q/(I+f)$. This is basically the statement that if $V\subset W$ are two varieties which both intersect a hypersurface $H$ properly, the intersection multiplicity of $V\cap H$ along any component $V'$ of $V\cap H$ is at least as large as the intersection multiplicity of $W\cap H$ along an irreducible component $W'$ of $W\cap H$ containing $V'$. I'm looking to prove this before saying something about it in my lecture when covering material related to Hartshorne I.7, but I'm having trouble finishing the argument.

The main tool that comes to mind is the fact that any finitely generated module over a noetherian ring $R$ has a finite filtration by submodules $M_i$ so that the subquotients $M_{i+1}/M_i$ are isomorphic to $R/\mathfrak{p}_i$ for $\mathfrak{p}_i$ a prime ideal of $R$, and the number of times a minimal prime shows up is the length of the module over that minimal prime. Unfortunately, I am a little rusty in this area and I can't quite finish the argument about how the filtrations of $S/(f)$ and $S/(I+f)$ relate to each other. It seems clear that I should take a filtration of one and either push it forward or pull it back along the obvious map $S/(f)\to S/(I+f)$ and argue from there, but I have had no further success.

One attempt: Localizing at $Q$, we get a finite filtration $\{M_i\}$ of $S_Q/(f)$ with subquotients $(S/\mathfrak{p}_i)_Q$ for $P\subset \mathfrak{p}_i\subset Q$. Under the quotient map $\alpha:S_Q/f\to S_Q/(I+f)$, we have that $\{\alpha(M_i)\}$ form a filtration of $S_Q/(I+f)$, and $M_{i+1}/M_i=S_Q/\mathfrak{p}_i$ surjects on to $\alpha(M_{i+1})/\alpha(M_i)$. If this latter module is nonzero, we're done - it has length at least one, so $\operatorname{length}_{S_Q} S_Q/(I+f)$ is at least the number of terms in the filtration of $S_Q/(f)$, which is at most the number of times $S_Q/P$ appears in that filtration. But I've been getting turned around in why this ought to be the case for a while, and I could use some help.

I'm looking for some help filling in the details of this argument. Alternate methods and suggestions are also welcome!

答:
I believe the desired result is not true. Let $S=\mathbb{Q}[x,y,z]\big/(xy-z^n)$, with $n\geqslant 2$. For convenience we refer to the coset $p+(xy-z^n)\in S$ as $\bar{p}$, for each $p\in\mathbb{Q}[x,y,z]$. Since $xy-z^n$ is irreducible in $\mathbb{Q}[x,y,z]$, $S$ is a domain. Now, let $f=\bar{x}$ and $P=(\bar{x},\bar{z})$. Note that if a prime ideal of $S$ contains $\bar{x}$, then it also contains $\bar{x}\bar{y}=\bar{z}^n$, and thus must contain $\bar{z}$, whence indeed $P$ is a minimal prime over $f$. Now let $I=(\bar{y},\bar{z})$ and take $Q=(\bar{x},\bar{y},\bar{z})$. Note that $I+(f)=I+P=Q$, so $Q$ is indeed a minimal prime over $I+(f)$ containing $P$. Since $I+(f)<S$ is proper, $f+I$ is not a unit in $S/I$. Also, $x\notin(y,z,xy-z^n)=(y,z)$, so $f=\bar{x}\notin (\bar{y},\bar{z})=I$, so $f+I$ is non-zero in $S/I$ and hence not a zero divisor there either. Thus all the conditions of your problem are satisfied.

However, in $S_P$, we have the chain of ideals $(f)_P=(\bar{x})_P<P_P<S_P,$ which is strictly ascending by the lemma below, and so $\operatorname{length}_{S_P}S_P/(f)_P\geqslant 2.$ On the other hand, in $S_Q$, we have $(I+(f))_Q=(I+P)_Q=Q_Q$, so $\operatorname{length}_{S_Q}S_Q/(I+(f))_Q=1$, and thus this provides a counterexample to your claim.

I'm not entirely sure what the geometric significance of this example is; thoughts would be welcome.

Lemma: If $\bar{x}$ and $P$ are as above, then $(\bar{x})_P\neq P_P$.

Suppose the contrary, so that $(\bar{x})_P=P_P$. Then $\bar{z}\big/1\in(\bar{x})_P$, and so there must be some $\bar{q}\in S\setminus P$ such that $\bar{q}\bar{z}\in(\bar{x})$; in other words, $qz\in(x,xy-z^n)=(x,z^n)$, as elements of $\mathbb{Q}[x,y,z]$. Suppose therefore that $qz=\lambda x+\mu z^n$ for some $\lambda,\mu\in\mathbb{Q}[x,y,z]$. Note that $\lambda x=z(q-\mu z^{n-1})$, and thus, since $\mathbb{Q}[x,y,z]$ is a UFD, $z$ divides $\lambda$; say $\lambda=z\lambda'$. Then we have $q=\lambda'x+\mu z^{n-1}\in (x,z)$, since $n\geqslant 2$, but this means $\bar{q}\in(\bar{x},\bar{z})=P$, a contradiction.

ContentLicense: CC BY-SA 4.0


问:
Function inflection point?
I have a normal function $f(x)=(x^{2}-1)^{\frac{2}{3}}$. Derivative $\frac{4x}{3(x^{2}-1)^{\frac{1}{3}}}$. Second derivative $\frac{4\left(x^2-3\right)}{9\left(x^2-1\right)^{\frac{4}{3}}}$. When I calculated it, is not normal. Because inflection point is $\sqrt{3}$ and $\sqrt{-3}$, but they are not like that when I graph it on geogebra? There is only critical point x=1,-1. How to solve this?

答:
Your intuition is correct. The second derivative is $\frac{4(x^2-3)}{9(x^2-1)^{\frac{4}{3}}}$. Setting the numerator equal to $0$ yields $4(x^2-3) = 0$, or $x = \sqrt{3}, -\sqrt{3}$. These are the correct inflection points. If you graph it, it doesn't look right only because the graph looks very straight. However, rest assured, the function DOES change concavity here.

Just note it's $-\sqrt{3}$, not $\sqrt{-3}$, which is imaginary.

Title: Function inflection point?


问:
Show the map $f(x)=\frac12 (x+1/x)$ has an attractive fixed point in $(0,\infty)$
From numerical test, I know $x=1$ is an attractive fixed point of the function
$$
f(x)=\frac12 \left(x+\frac{1}{x}\right),
$$
on $(0,\infty)$.

Is there a way to prove it?

Since
$$
f'(x)=\frac12\left(1-\frac{1}{x^2}\right),
$$
then
$$
|f'(x)| < 1,
$$
on $[1,\infty)$, and Banach contraction principle gives the result.

But how to proceed for $(0,1)$?

Let $a_0 \in (0,1)$ and choose
$$
0< \epsilon < a_0,
$$
then the derivative is bounded on $(\epsilon,\infty)$.

But I don't see how to build a contraction on $(\epsilon,\infty)$, which gives the result.

I tried
$$
g(x)=\frac{1}{M}f(x),
$$
with
$$
M=\sup\{x\in(\epsilon,\infty):|f'(x)|\}+1,
$$
but it doesn't work.

答: Since $f(x)=f\left(\frac 1 x\right)$, once proven for $x > 1$ that $f^{(n)}(x)\xrightarrow[n\to\infty]{} 1$, then you get it for $x\in(0,1)$ "for free".</p>

ContentLicense: CC BY-SA 3.0


问:
prove this summation by case analysis
How would I go about trying to prove the below via case analysis?
$$\sum_{i=1}^n i = \frac{(n)(n+1)}{2}$$

I understand that you'd need to split it up into two cases, when n is odd and n is even. But anything aside that I need a little help with.

Here's the notes with the incorrect proof I was working from: Screen print of proof question and work through

答:
You are misreading the graphic.

To make sense of the proof in (for example) the case of $n = 2k$

First  consider that

$$\sum_{i=k+1}^{2k} (i) ~=~ \sum_{i=1}^k (2k + 1 - i).$$

The easiest way to see this is to consider that having $i$ range from
$(k+1)$ to $(2k)$, is equivalent to having $i$ range downward from
$(2k)$ to $(k+1)$.  Examining the terms in reverse order, you have
$(2k) + (2k-1) + \cdots + (k+1).$

This alternate perspective is consistent with $\sum_{i=1}^k (2k + 1 - i).$

The remainder of the proof in the case of $n = 2k$ is therefore valid.

Title: prove this summation by case analysis


问:
Burgers' equation $u_y + uu_x = 0$ with $u(x,0)=-x$
I couldn't solve this problem, can you help me please?

The Burgers' equation

$$ u_y + uu_x = 0 $$ $ - \infty < x < \infty $ , $ y > 0 $ , $ u(x,0)=f(x) $

My question;

is there any solution $ f(x)= -x $ for all $ y>0 $ , if not, why?

Thank you for your help.

答:
As discussed in the other answers and this post, the method of characteristics yields the classical solution $u = -(x-uy)$, i.e. $$
u(x,y) = \frac{-x}{1-y} \, .
$$
Obviously, the denominator vanishes when $y$ reaches unity: the classical solution breaks down as $y\to 1$. This is reflected by the computation of the breaking time $$
y_b = \inf \frac{-1}{(-\text{id})'(x)} = 1 \, .
$$ There, all the characteristic curves intersect simultaneously (cf. picture in answer by @cool), i.e. the solution $u$ takes simultaneously all the values from $−∞$ to $+∞$. It literally blows up! There is no weak solution (e.g. of shock-wave type) to start after this blow-up happened.


问:
How is material implication the same as subset?
I've been told and read a number of times that implies, $\implies$, is the same as subset $\subseteq$. For example, in the wikipedia page on iff it states that "P only if Q", "if P then Q", and "P→Q" all mean that P is a subset, either proper or improper, of Q

I'm currently thinking in terms of propositional logic, and I don't understand how it makes sense to say that $P \implies Q$ means that $P$ is  a subset of $Q$. To my current understanding, $P$ and $Q$ are both propositions, which means that they are in the set $\{T,F\}$. This set contains only two elements and neither of them are sets, so how can $P$ be a subset of $Q$?

I know that the two element Boolean algebra can be realised using  $T = \{\emptyset\}$ and $F = \emptyset$, along with intersection union and complement. Then this would mean that I can represent $\implies$ using $\subseteq$, because $\emptyset \subseteq \{\emptyset\}$ etc. to give the correct truth table, but I don't see how that could relate $P \implies Q$ to $P \subseteq Q$.

I think when I'm told that $P \implies Q$ means that $P \subseteq Q$, this must be somehow taking the space of all propositions (perhaps for some specific set of axioms?) and then $P \subseteq Q$ in that space would mean that $P \implies Q$, is this correct? Can anyone elaborate on how this works and direct me to any related reading?

答:
It's certainly not the case that implication "is" subsethood, since - as you say - that's mixing up types of objects.

However, note that in the wiki page, the relevant claim appears within the section on Euler diagrams: so it's not an absolute statement, but rather a statement about how Euler diagrams interpret sentences. And there's much less here than meets the eye: by definition, an Euler diagram for a collection of sentences is a diagram with regions corresponding to sentences where subsethood matches implication.

That said, there is a nontrivial interpretation of Euler diagrams. Specifically, to a sentence $P$ we can associate the set of "models" of $P$, $Mod(P)$, which you can think of as the ways in which $P$ can be true. Then we do indeed have a match up between impication and subsethood: the sentence "$P\rightarrow Q$" is provable from the laws of logic alone (= is a tautology) iff $Mod(P)\subseteq Mod(Q)$. See also these old answer of mine: 1, 2.

More generally, we have that $P\rightarrow Q$ is provable from some theory $T$ iff $Mod(T\cup\{P\})\subseteq Mod(T\cup\{Q\})$, where for $\Gamma$ a set of sentences we define $$Mod(\Gamma):=\bigcap_{\gamma\in\Gamma}Mod(\gamma)$$ (that is, $Mod(\Gamma)$ is the set of structures which are simultaneously models of all the sentences in $\Gamma$).


问:
A problem on the binomial theorem
Find $x, y$ such that

$$x^3 + c(3,1)x^2 y + C(3,2)xy^2 + y^3 = 64$$

and

$$x^5 - C(5,1)x^4y + C(5,2)x^3y^2 - C(5,3)x^2 y^3 + C(5,4)xy^4 - y^5 = 32.$$

I might solve this problem by inspection, but I'm really after what the question author intended here.  I know $(x + y)^3 = 64$ but $(x + y)^5 \ne 32$.  The author introduced some negative terms, so it's not the binomial expansion and I can't seem to catch on to the idea.

I can see the problem is interested in powers of two.  I know $2^6 = (2^2)^3= 64$ so for the first equation, it seems that $x + y = 4$, but there's an infinite number of solution there.  I don't quite get what the minus signs on the second equation are trying to tell me.  How should I approach this?

答: Hint: In addition to considering binomial expansions of $(x+y)^n$, also consider binomial expansions of $(x-y)^n=\left[x+(-y)\right]^n$.

Title: A problem on the binomial theorem


问:
Identity of inverse matrix
How can I prove that

$$(C_{N}^{-1} + W_{N})^{-1} = C_{N}(I + W_{N}C_{N})^{-1}$$

I tried to use the Woodbury identity:

$$(A + BD^{-1}C)^{-1} = A^{-1}-A^{-1}B(D+CA^{-1}B)^{-1}CA^{-1}$$

which seems to be useful in this case, but I can't simplify enough to get the result.

Suggestions?

答: What happens when you just multiply the RHS by $C_N^{-1} + W_N$?</p>

Title: Identity of inverse matrix


问:
Rings without identity and non-isomorphic ring structure on $\mathbb{Z}$
I am solving Exercise 2.15 from Aluffi chapter 0.

Exercise 2.15. For $m > 0$ , the abelian group $(\mathbb{Z},+)$ and $(m\mathbb{Z},+)$ are manifestly isomorphic: the function $\phi : \mathbb{Z} \rightarrow m\mathbb{Z}$ given by $n \mapsto nm$ is a group isomorphism. Use this isomorphism to transfer the structure of "ring without identity" $(m\mathbb{Z},+,*)$ back onto $\mathbb{Z}$: Give an explicit formula for the "multiplication" this defines on $\mathbb{Z}$. Explain why structures induced by different positive integer m are non-isomorphic as "rings without 1".

Solution:

We have the following map:

$\phi : \mathbb{Z} \rightarrow m\mathbb{Z}$ given by $n \mapsto nm$. We can use this map to transfer ring structure on $\mathbb{Z}$ as follows:

Let $s_1,s_2 \in \mathbb{Z}$ and set $s_1 s_2 = m (s_1 s_2)$. This defines ring structure on $\mathbb{Z}$. This ring structure is non-isomorphic because if we have $s_1 s_2 = m (s_1 s_2) = n (s_1 s_2)$ then we would have n = m for $n \neq m$. Is my my argument valid ?

答: You're almost there. What you showed in the end is that the identity map is not a ring homomorphism from $\mathbb Z$ with $n$ multiplication to $\mathbb Z$ with $m$ multiplication. So indeed this is not an isomorphism. However, a priori there could be some other isomorphism. However, the only group homomorphisms $\mathbb Z \longrightarrow \mathbb Z$ are multiplication by some fixed integer, so the only group isomorphisms are multiplication by the units $\pm 1$. You've shown that the identity map is not a ring isomorphism, so it remains to consider multiplication by $-1$. But since you restricted to $m > 0$, this won't work either. Hence, these rings are not isomorphic.


问:
Showing something is an integral domain
I asked a similar question earlier so I decided to rephrase as I was a little confused. I am trying to figure out if the quotient ring over the ideals below is an integral domain.

So for an integral domain we have to have a non zero commutative ring with no zero divisors ($f(x)g(x)=0$ to be a zero divisor, where $f(x),g(x)$ are non zero). I know that both of these are rings but I am trying so see if they each have zero divisors.

a) $\langle (x+1)(x+2)\rangle $

b) $\langle (x^3+x^2+x+2)\rangle $

For the first one if we expand we get $x^2+3x+2$, then trying $x=0,1,2$ we cannot multiply any of these subbed into our polynomial to make zero, hence there are no zero divisors hence it is an integral domain?

For the second one, again I can't find any $f(x), g(x)$ to make zero. So again I would say this is an integral domain. However I am unsure on both could anyone help me out?

答:
I presume you're looking at the quotient of the polynomial ring ${\mathbb F_3}[x]$ by a) the ideal $I = \langle (x+1)(x+2)\rangle$ and b) the ideal $I = \langle x^3 + x^2 + x + 2\rangle$.

So the question is if there are two polynomials $f(x), g(x) \in {\mathbb F}_3[x]$ that are non-zero modulo $I$, but whose product is $0$ modulo $I$.

For a), such polynomials exist by constuction: $f(x) = x+1$ and $g(x) = x+2$ will do.

For b), it takes a bit more work that such polynomials do not exist. It boils down to showing that $x^3 + x^2 + x + 2$ is irreducible modulo $I$. Because its degree is $3$ that boils down to showing that it has no roots in ${\mathbb F}_3$.

Title: Showing something is an integral domain


答:
Consider this interpretation: $P$ and $Q$ aren't elements of $\{T, F\}$, but rather functions from some sensible domain to $\{T, F\}$. For some simple examples, on the domain of natural numbers, consider

$A(n)= n\text{ is even}$

$B(n)=n\text{ is a square}$

$C(n)= n\text{ is prime}$

In this interpretation, $P\implies Q$ means

(On the implied domain,) $Q(n)$ is true for any $n$ that makes $P(n)$ true

This can be reformulated in terms of $\subseteq$ as
$$
\{n\mid P(n)\}\subseteq \{n\mid Q(n)\}
$$
This doesn't make $\implies$ into $\subseteq$, but they are quite closely related.

Also, it might be worth noting that the very definition of $X\subseteq Y$ is
$$
x\in X\implies x\in Y
$$
where the domain is the universe of all sets.

As noted by Noah Schweber, this runs into some issues when you get into the nitty-gritty of formal logic and modern set theory. But for other branches, like number theory, analysis or algebra, this level of rigor is just fine.

Title: How is material implication the same as subset?

Body:
I've been told and read a number of times that implies, $\implies$, is the same as subset $\subseteq$. For example, in the wikipedia page on iff it states that "P only if Q", "if P then Q", and "P→Q" all mean that P is a subset, either proper or improper, of Q

I'm currently thinking in terms of propositional logic, and I don't understand how it makes sense to say that $P \implies Q$ means that $P$ is  a subset of $Q$. To my current understanding, $P$ and $Q$ are both propositions, which means that they are in the set $\{T,F\}$. This set contains only two elements and neither of them are sets, so how can $P$ be a subset of $Q$?

I know that the two element Boolean algebra can be realised using  $T = \{\emptyset\}$ and $F = \emptyset$, along with intersection union and complement. Then this would mean that I can represent $\implies$ using $\subseteq$, because $\emptyset \subseteq \{\emptyset\}$ etc. to give the correct truth table, but I don't see how that could relate $P \implies Q$ to $P \subseteq Q$.

I think when I'm told that $P \implies Q$ means that $P \subseteq Q$, this must be somehow taking the space of all propositions (perhaps for some specific set of axioms?) and then $P \subseteq Q$ in that space would mean that $P \implies Q$, is this correct? Can anyone elaborate on how this works and direct me to any related reading?


答:
Use the inequality $x+\frac{1}{x}\ge 2$, which can be proved many ways. For example, we can note that $\left(\sqrt{x}-\frac{1}{\sqrt{x}}\right)^2\ge 0$. Or else we can quote AM/GM.

Remark: The fixed point is in fact very attractive, since the derivative there is $0$.

Title: Show the map $f(x)=\frac12 (x+1/x)$ has an attractive fixed point in $(0,\infty)$

Body:
From numerical test, I know $x=1$ is an attractive fixed point of the function
$$
f(x)=\frac12 \left(x+\frac{1}{x}\right),
$$
on $(0,\infty)$.

Is there a way to prove it?

Since
$$
f'(x)=\frac12\left(1-\frac{1}{x^2}\right),
$$
then
$$
|f'(x)| < 1,
$$
on $[1,\infty)$, and Banach contraction principle gives the result.

But how to proceed for $(0,1)$?

Let $a_0 \in (0,1)$ and choose
$$
0< \epsilon < a_0,
$$
then the derivative is bounded on $(\epsilon,\infty)$.

But I don't see how to build a contraction on $(\epsilon,\infty)$, which gives the result.

I tried
$$
g(x)=\frac{1}{M}f(x),
$$
with
$$
M=\sup\{x\in(\epsilon,\infty):|f'(x)|\}+1,
$$
but it doesn't work.


问:
Traverse all permutations of pairs, triples, etc. in a minimal number of batches?
I have a collection of test cases $t_1, \ldots, t_n$ for my software. I suspect my tests themselves have a bug, in which some of them share global state and fail if run in the right order.

I would like to find this by running all tests in some order. If the run fails, I'll employ a minimization technique to find a smallest example. Otherwise, my plan is to run the test suite in a different order until I find a failure or give up.

I would like to choose the order in which I run my tests intelligently. For example, if on the second run I run the test cases in the reverse order of the first, the following holds: for every pair of test cases $t_i$ and $t_j$, I have performed one run in which $t_i$ came before $t_j$ and one run in which $t_j$ came before $t_i$.

I would like to achieve something similar for triples of test cases, in $3! = 6$ runs. However, my own exhaustive search suggests that for $n \geq 5$ this is impossible.

What is the smallest number $k$ such that there exists $k$ permutations of $\{1, \ldots, n\}$ containing all triples in all orders between them? Is there a simple scheme for generating such permutations? Is there a scheme which tries all $m$-tuples, for each $m$?

For $n = 4$ the set of permutations $(0, 1, 2, 3), (0, 3, 2, 1), (1, 3, 0, 2), (2, 1, 0, 3), (2, 3, 0, 1), (3, 1, 2, 0)$ tries all triples. One notes that $(0, 1, 2, 3)$ is here but $(3, 2, 1, 0)$ isn't. Is it ever possible to be optimal with respect to both pairs and triples? (i.e. try all orderings of pairs with the first two permutations and all triple-orderings with the first however-many-it-takes permutations)? Is it possible to be optimal with respect to all tuple sizes simultaneously?

答:
I will answer a similar question which I believe may solve your problem, but it will not be a direct answer to the question for $k$. Instead of running $k$ permutations of the tests, you may be satisfied with generating a single sequence (longer than $n$, repeating some tests) containing every possible permutation of length $3$ as a subsequence. A general problem is known as Shortest Common Supersequence Problem (SCS for short), which given a set of strings $S = \{s_1, \dots, s_m\}$ (in your case the strings are permutations of length 3) asks for the shortest string $X$ containing each $s_i$ as a subsequence.

While it was shown that for an arbitrary set $S$ the problem is NP-hard, there exists quite an old research of Newey which may be found here which covers exactly the topic of finding SCS when $S$ is a set of all permutations of some alphabet $A$ of given length $m$. You may be especially interested in statement 2.10:
$$M'(n, 3) = 3n-2$$
saying that the length of SCS containing every 3-permutation of $n$ elements is equal to $3n-2$. That means that there exists a sequence $X$ having length $3n-2$ of the tests such that for every triple of tests each of their permutations will be a subsequence of this SCS. What is even better, Newey gives an algorithm to generate such a sequence in section 8. I will rewrite this code in R (the indices in R start from $1$ instead of $0$, so beware)

```<code>A <- 1:7 #There are seven tests in that case
SCS <- c()
n <- length(A)
m <- 3
B <- A[(n-m+2):n]
SCS <- c(SCS, A)
for(i in 1:(m-2)){
  SCS <- c(SCS, A[1:(n-m+1)])
  SCS <- c(SCS, B[1:(m-2)])
  B <- c(B[m-1], B[1:(m-2)])
}
SCS <- c(SCS, A[1:(n-m+1)])
SCS <- c(SCS, B[1])
SCS
</code>```

Using SCS you naturally satisfy that every $2$-permutation is covered as well, which would not be obvious if you used $k$ permutations. Moreover, the above code works for any $m$ and guarantees that every $i$-tuple of elements for $i \in \{1, \dots, m\}$ is a subsequence of the SCS having length $mn-3m+4$.

Body:
I will answer a similar question which I believe may solve your problem, but it will not be a direct answer to the question for $k$. Instead of running $k$ permutations of the tests, you may be satisfied with generating a single sequence (longer than $n$, repeating some tests) containing every possible permutation of length $3$ as a subsequence. A general problem is known as Shortest Common Supersequence Problem (SCS for short), which given a set of strings $S = \{s_1, \dots, s_m\}$ (in your case the strings are permutations of length 3) asks for the shortest string $X$ containing each $s_i$ as a subsequence.

While it was shown that for an arbitrary set $S$ the problem is NP-hard, there exists quite an old research of Newey which may be found here which covers exactly the topic of finding SCS when $S$ is a set of all permutations of some alphabet $A$ of given length $m$. You may be especially interested in statement 2.10:
$$M'(n, 3) = 3n-2$$
saying that the length of SCS containing every 3-permutation of $n$ elements is equal to $3n-2$. That means that there exists a sequence $X$ having length $3n-2$ of the tests such that for every triple of tests each of their permutations will be a subsequence of this SCS. What is even better, Newey gives an algorithm to generate such a sequence in section 8. I will rewrite this code in R (the indices in R start from $1$ instead of $0$, so beware)

A <- 1:7 #There are seven tests in that case
SCS <- c()
n <- length(A)
m <- 3
B <- A[(n-m+2):n]
SCS <- c(SCS, A)
for(i in 1:(m-2)){
  SCS <- c(SCS, A[1:(n-m+1)])
  SCS <- c(SCS, B[1:(m-2)])
  B <- c(B[m-1], B[1:(m-2)])
}
SCS <- c(SCS, A[1:(n-m+1)])
SCS <- c(SCS, B[1])
SCS

Using SCS you naturally satisfy that every $2$-permutation is covered as well, which would not be obvious if you used $k$ permutations. Moreover, the above code works for any $m$ and guarantees that every $i$-tuple of elements for $i \in \{1, \dots, m\}$ is a subsequence of the SCS having length $mn-3m+4$.


问:
to show a quotient space of group action is not Hausdorff
Consider the group $\mathbb{Z}$ acting on $\mathbb{R}^2-\{(0,0)\}$ by $n\cdot(x,y)=(2^nx,2^{-n}y)$. How do we know the quotient space $\mathbb{R}^2-\{(0,0)\}/\mathbb{Z}$ is not Hausdorff?

答:
When asking questions like yours on this website, it's a good idea to tell us what you've tried already, so that answers can be tailored to fit your needs.  Since I don't know where you're stuck, here are some hints to guide you.

HINT 1: What does it mean for $(\mathbb{R}^2 \setminus \{(0,0)\}) / \mathbb{Z}$ to be Hausdorff or not Hausdorff?

 $(\mathbb{R}^2 \setminus \{(0,0)\}) / \mathbb{Z}$ is Hausdorff if for all $x, y \in \mathbb{R}^2 \setminus \{(0,0)\}$ such that $\mathbb{Z} \cdot x \neq \mathbb{Z} \cdot y$, there exists open neighborhoods $U \ni x$, $V \ni y$ in $\mathbb{R}^2 \setminus \{(0,0)\}$ such that $\mathbb{Z} \cdot U \cap \mathbb{Z} \cdot V = \emptyset$.

 Therefore, to show that $(\mathbb{R}^2 \setminus \{(0,0)\}) / \mathbb{Z}$ is not Hausdorff, you need to exhibit two points $x$ and $y$ from different orbits such that for every pair of open sets $U \ni x$, $V \ni y$ containing them, the orbits of $U$ and $V$ intersect.

HINT 2: How do you show a violation of Hausdorffness for $(\mathbb{R}^2 \setminus \{(0,0)\}) / \mathbb{Z}$?

 Take $x = (1, 0)$ and $y = (0, 1)$.  If you take a look at their orbits, it appears that they accumulate at the origin.  So while the orbits of $x$ and $y$ are different, it seems that open neighborhoods around these orbits will have to overlap close to the origin.  Can you show that this is the case for every pair of neighborhood containing $x$ and $y$?

If you're still stuck, here's another hint.

 Let $U$ be an open neighborhood of $x = (1,0)$ and $V$ an open neighborhood of $y = (0,1)$.  By shrinking these sets, we may assume without loss of generality that $U = (1 - \epsilon, 1 + \epsilon) \times (-\epsilon, \epsilon)$ and $V = (-\epsilon, \epsilon) \times (1 - \epsilon, 1 + \epsilon)$ for some $0 < \epsilon < 1$.  The group $\mathbb{Z}$ acts on these sets by \begin{align*} m \cdot U &= (2^m (1 - \epsilon), 2^m (1 + \epsilon)) \times (-2^{-m} \epsilon, 2^{-m} \epsilon) \\ n \cdot V &= (-2^n \epsilon, 2^n \epsilon) \times (2^{-n} (1 - \epsilon), 2^{-n} (1 + \epsilon)), \end{align*} for $m, n \in \mathbb{Z}$.  Can you find $m, n$ (depending on $\epsilon$) such that $m \cdot U$ and $n \cdot V$ intersect?

Here is one last hint:

 Take $m = -n$, and $n > \frac{1}{2} \log_2(\frac{1-\epsilon}{\epsilon})$ in the previous hint.


问:
If the transformation T is an isometry, then the column vectors of [T] form an orthonormal set.
I'm not sure how to attack this problem at all. An isometric transformation preserves length of vectors, but I can't make any connections.</p>

答: Hint:  Apply to the standard basis, which is orthonormal.  You see, $T$, since defined on a finite dimensional vector space, also preserves angles, by the usual definition of isometry.


问:
Divide by a number without dividing.
Can anyone come up with a way to divide any given x by any given y without actually dividing?

For example to add any given x to any given y without adding you would just do:

$x-(-y)$

And to subtract any given x from any given y (that is, y-x) you could do:

$y+xe^{iπ}$

*edit: well since (i) is ($\sqrt{-1}$) and that is technically subtracting this one might not work perfectly but for the sake of the riddle and for the sake of example, I'm using that equation :)

How can you divide without dividing? Can anyone come up with equations that work for all $x$ and $y$ values? (For all intents and purposes we will leave out dividing by zero issues and what-not... don't worry about that...

答: For $y \neq 0$ $$\large x\div y = \dfrac 1y\times x = y^{-1}\times x = \large y^{\left(e^{i\pi}\right)}\times x = y^{\left(i^2\right)}\times x$$</p>

Title: Divide by a number without dividing.


答:
Material Implication is a Logical Operation  in propositional logic. Whilst taking a subset is a mathematical operation in set theory.

They are not the same.

However, just as we use maths to model physical phenomena we can also use math to model logical phenomena. This was the insight of Boole.

Hence, when we use set theory to model propositional logic it turns out that the implication is modelled by taking subsets. In fact, in early notation of set-theoretic propositional logic the implication was denoted with the subset symbol. However, there is the possibility of confusing the senses and so eventually this was replaced by the usual symbol for implication: the double arrow.

The Material Implication should be distinguished from another sense of this, where it's not a Logical Operation but a Rule of Inference and replaces a conditional statement with a proposition involving 'and' and 'negation'.


问:
Linear programming with a second decision variable in the constraint vector
Is the following optimization problem feasible (modified optimal transport)? The primary decision variable appears in the objective function as $\mathbf{x}$,  whereas the second decision variable $\mathbf{y}\in \mathbb{R}^K$ is introduced in the constraint vector $\mathbf{b}$: This variable will be optimized as an optimal weight vector for multiplication against a multivariate data matrix $\mathbf{M}\in \mathbb{R}^{N\times K}$ as shown in the last bullet point. Product $\mathbf{M} \cdot \mathbf{y}$ therefore is an optimally weighted version of the original matrix, or optimal source distribution, but of size $N\times 1$.

$$
\begin{array}{rrcl}
\arg \min_{\mathbf{x}, \, \mathbf{y}} \ & \mathbf{c}^\top \mathbf{x} &  & \ \\
\mathrm{s.t.} \ & \mathbf{A} \mathbf{x} & = & \ \mathbf{b} \\
 \  & \mathbf{x} & \geq &\ \mathbf{0}
\end{array}$$

$\mathbf{c}$ is a vectorization of the distance matrix $\boldsymbol C$,

$\mathbf{x}$ is a vectorization of the transport matrix  $\boldsymbol\Gamma$,

while the source and target distributions are $\mathbf{b} = \begin{bmatrix} \mathbf{M} \cdot \mathbf{y}\\ \beta\end{bmatrix}$

Any comments on this optimization set-up with two decision variables would be helpful.

(Next issue is how to make standard solvers like scipy.optimize.linprog admit the existence of a second decision variable, because the documentation of most solvers only addresses one decision variable only. but I ask this part at stack instead)

答:
Your objective function can be written as $c^T x + 0^T y$.
Your constraints can be written in block-matrix form with constant RHS as follows, where the subscripts indicate the sizes:
$$
\begin{pmatrix}
A'_{\ell \times n}  & -M_{\ell \times K}\\
A''_{\ell \times n} & 0_{\ell \times K}\\
\end{pmatrix}
\begin{pmatrix}
x_{n \times 1}\\
y_{K \times 1}\\
\end{pmatrix}
=
\begin{pmatrix}
0_{\ell \times 1}\\
\beta_{\ell \times 1}\\
\end{pmatrix}
$$

If your solver requires a single vector of decision variables, then rename $y$, as described by @MichalAdamaszek.  Explicitly, $$(x_1,\dots,x_n,y_1,\dots,y_K)$$ becomes $$(x_1,\dots,x_n,x_{n+1},\dots,x_{n+K}).$$


问:
Parametrization composed with diffeomorphism is again a parametrization.?

Let $\phi : U\subset R^2 \to S$ be a local parametrization(local chart) of regular
surface $S$ and let $\sigma: V\subset R^2 \to U $ be a diffeomorphism. Then prove
that $\phi \circ \sigma : V \to S$ is also a local parametrization of
the surface $S$

I am given that the surface is regular and $\phi : U\subset R^2 \to S$ is one of the local parametrization. This means that $\phi$ is smooth, homeomorphism ($\phi$ is continuous, and has a continuous inverse) and the jacobian matrix of $Df : U \to S$ has rank $2$, i.e, the linear transformation $Df$ is one-one

I know that $\sigma$ being diffeomorphism means that it is smooth and has a smooth inverse.

Since I already know that $S$ is smooth, I need to show only the following:

$\phi \circ \sigma$ is smooth, which is true because it is composed of two smooth functions

The jacobian matrix of $D(\phi \circ \sigma) = D(\phi(\sigma))_{3\times 2}\times D(\sigma)_{2\times 2}$ has rank $2$. I am struggling in proving this.

$\phi \circ \sigma$ is one-one. I am also struggling in providing an accurate argument why this is true.

Please help me filling the gaps.

答:
Right.

Multiplying a matrix by a square non-singular matrix, by either side, preserves rank.

A composition of two one-to-one functions is also one-to-one.


问:
How do we show this variety is normal?
I just saw my question is closed. I think I need to provide some details.

Suppose $X$ is a variety over a field $k$ and $f: X\to S=\mathbb{A}_{k}^{1}=\operatorname{Spec}(k[t])$ is a flat morphism. Assume the restriction of the morphism $f$ over $\operatorname{Spec}k[t,1/t]$ is smooth and the fiber over $t=0$ is an integral scheme. I want to show that $X$ is normal.

After thinking for a long time, I think we may use Serre’s $R_{1}+S_{2}$ to prove it. For $R_{1}$, it is clear, since the fiber over $0$ is integral, the singular point in this fiber cloud just be an proper closed subset of the fiber. Since other fibers are smooth, all singular locus could just be a codimension 2 subset. So it is regular codimension.

Notice we do not use flat to prove $R_{1}$, so I think we need to use flat to prove $S_{2}$. But I do not how to do it.

答:
Note that you did actually use flatness for $R_1$: this gives you that $X\to \Bbb A^1$ is open, so the fiber over $0$ is of positive codimension. We will be using flatness for $S_2$, though.

For $S_2$, note first that this condition is satisfied on the preimage of $\Bbb A^1_k\setminus \{0\}$ in $X$: this is smooth. Therefore we just need to check this condition on the fiber $X_0$. If $X_0$ is empty, we're done, else let $x\in X_0$ be arbitrary. By flatness, the image of $t$ along the map $k[t]_{(t)}=\mathcal{O}_{\Bbb A^1_k,0}\to \mathcal{O}_{X,x}$ is not a zero-divisor. But $\mathcal{O}_{X,x}/t \cong \mathcal{O}_{X_0,x}$ - if this is a field, then the height of $\mathfrak{m}_x$ is one, and if not, we can pick a non-zero-divisor in the maximal ideal of $\mathcal{O}_{X_0,x}$ by the assumption $X_0$ is integral. So in the first case, we've shown that the depth of $\mathcal{O}_{X,x}$ is at least the height of $\mathfrak{m}_x$ by finding a regular sequence of length one, and in the second, we've shown it's at least 2 by finding a regular sequence of length two - thus we've shown that $X$ satisfies $S_2$ and is normal.

Title: How do we show this variety is normal?


问:
Compositions of $n$ with largest part at most $m$
This is a problem from Stanley's Enumerative Combinatorics that I'm failing at a bit (lot):

Let $\bar{c}(m,n)$ denote the number of compositions of $n$ with largest part at most $m$.  Show that $$\sum_{n\geq 0}\bar{c}(m,n)x^n={{1-x}\over{1-2x+x^{m+1}}}$$

Some definitions:  A composition of $n$ is an $ordered$ list of positive integers that equals $n$.  If $\{a_1,...,a_k\}$ is one such composition, we say that the composition has $k$ $parts$.

I know it's pretty traditional to list a "what you've done so far" but I'm really about as blindly stuck as can be.

答:
I tried my own way and got something slightly different - more on that in a second. Let $c(m,n,k)$ be the number of integer compositions with largers part $\le m$ and exactly $k$ parts. Then

$$\sum_n c(m,n,k)x^n=\left.\sum_{p_1=1}^m\cdots\sum_{p_k=1}^m x_1^{p_1}\cdots x_k^{p_k}\right|_{x_1=x_2=\cdots=x_k=x}=\left(x\frac{1-x^m}{1-x~~~}\right)^k$$

and therefore

$$\sum_n c(m,n)x^n=\sum_n\left[\sum_{k\ge1}c(m,n,k)\right]x^n=\sum_{k\ge1}\sum_nc(m,n,k)x^n$$

$$=\sum_{k\ge1}\left(x\frac{1-x^m}{1-x~~~}\right)^k=\frac{\displaystyle x\frac{1-x^m}{1-x~~~}}{\displaystyle 1-x\frac{1-x^m}{1-x~~~}}=\frac{x(1-x^m)}{1-2x+x^{m+1}}.$$

Note that

$$\frac{x(1-x^m)}{1-2x+x^{m+1}}=\frac{1-x}{1-2x+x^{m+1}}-1,$$

so the given answer and mine differ merely by $1$. What's the deal? The reason we need to add $1$ I presume is that $n=0$ has one integer composition, namely the empty set (it is the empty sum). At least that's what OEIS says, I haven't actually seen the textbook's definition/convention for $0$.


问:
Product of monic polynomials in finite fields
I am trying to show that the product of monic polynomials of degree $n$ in $\mathbb{F}_p[T]$ is given by $\prod_{i=0}^{n}(T^{p^n}-T^{p^i})$. I tried generating function but with no luck. Any hint?</p>

答:
Let $P_n(T)$ be the product of all monic polynomials of degree $n$ in $\mathbb{F}_p[T]$. We can show that $P_n(T)=\prod_{i=0}^{n-1}(T^{p^n}-T^{p^i})$ (the bounds on the product were slightly off as stated in the original question). Clearly $P_1(T)=T^p-T$, so for induction purposes, it suffices to show that $P_n(T)=(T^{p^n}-T)\cdot P_{n-1}(T)^p$.

Consider the unique factorization of $P_n(T)$ into irreducible factors. Let $g(T)\in \mathbb{F}_p[T]$ be irreducible and denote $m=\deg(g)$. Set $k=\lfloor n/m \rfloor$. The number of times $g(T)$ shows up in the factorization of $P_n(T)$ is given by
\begin{align*}
\text{ord}_g(P_n)=\sum_{i=1}^k f_i
\end{align*}
where $f_i$ is the number of distinct monic polynomials of degree $n$ in $\mathbb{F}_p[T]$ divisible by $g(t)^i$. In other words, $f_i$ is equal to the number of monic polynomials of degree $n-im$ in $\mathbb{F}_p[T]$, i.e. $f_i=p^{n-im}$.

This shows that
\begin{align*}
\text{ord}_g(P_n)= \begin{cases}
p\cdot\text{ord}_g(P_{n-1}), &&\text{if}\; m\nmid n,\\
p\cdot\text{ord}_g(P_{n-1}) + 1, &&\text{if}\; m\mid n.
\end{cases}
\end{align*}

We arrive at
\begin{align*}
P_n(T)&=\bigg(\prod_{\substack{g \text{ irreducible, monic}\\\deg(g)\mid n}} g(T)\bigg)P_{n-1}(T)^p\\
&=(T^{p^n}-T)P_{n-1}(T)^p,
\end{align*}
which proves the claim.


问:
Amplitude of wave question
Suppose the following wave has amplitude 1.

$y(x,z,t)=Ab\cos(px)e^{iwt+ikz}$

Find a relationship between $A$ and $b$. Then rewrite $y$ in terms of that relationship.

My thoughts.

The amplitude is the largest value $y$ can take. So $|Abcos(px)e^{iwt+ikz}|=|Ab|=1$.

Is that all that is required?

答: Honestly, yes. In fact, $|Ab|=1$ means that $Ab= 1$ or $Ab=-1$, so either $$y(x,z,t) = \cos(px) {\rm e}^{{\rm i}\omega t+ {\rm i}kz} \quad \mbox{or}\quad y(x,z,t) = \cos(px) {\rm e}^{{\rm i}\omega t+ {\rm i}kz}.$$I wonder why you were even asked this --- the expression for $y(x,z,t)$ being more complicated than the usual $y = A\cos(Bx-C)+D$ people see in precalculus classes would suggest something more is going on, but oh well.

Title: Amplitude of wave question


问:
Prove $SPAN(S)$is the smallest subspace of $V$ that contains the vectors $v_1,...,v_p$.
Let $V$ be a vector space and $S=${$v_1,...,v_p$} be a set in in $V$. Prove $SPAN(S)$is the smallest subspace of $V$ that contains the vectors $v_1,...,v_p$.

Proof: let $B=${$v_1,...,v_n$} with $n≤p$ be a subset of $S$ and also a basis for $SPAN(S)$, then $SPAN(S)=SPAN(B)$. Now, assume that there is a smaller basis {$v_1,...,v_{n-1}$} s.t. $SPAN(v_1,...,v_{n-1})=SPAN(B)$. Because $B$ is linearaly independent $v_n$ is not a linear combination of {$v_1,...,v_{n-1}$}, so $v_n∉SPAN(v_1,...,v_{n-1})=SPAN(B)$, but this is a contradiction as $v_n∈SPAN(B)=SPAN(S)$. Therefore $SPAN(S)$is the smallest subspace of $V$ that contains the vectors $v_1,...,v_p$.

Please comment and provide feedback on the validity of my proof. Thank you.

答:
Your proof assumes that, given a set $S=\{v_1,\ldots,v_p\}$, then there is a $n\leqslant p$ such that $\{v_1,\ldots,v_n\}$ is a basis of $\operatorname{span}(S)$. That is not true. For instance, if $v_1=0$ and $v_2\ne0$, then there is no such $n$.

You can do it as follows. Let $W$ be a subspace of $V$ such that $W\supset S$. Then, since $W\supset S$ and since $W$ is a vector space, $W$ contains all linear combinations of elements of $S$. In other words, $W\supset\operatorname{span}(S)$. This proves that $\operatorname{span}(S)$ is contained in every subspace of $V$ containing $S$. Therefore, since $\operatorname{span}(S)$ is a subspace containing $S$, it is the smallest such subspace.


问:
Find the area of the surface defined by $x-y-z=1$ and $2x^2+y^2 \leq 1$

Find the area of the surface defined by $x-y-z=1$ and $2x^2+y^2 \leq 1$

I've tried to solve this using Green's theorem, but I'm not getting the correct answer.

The curve I get when I intersect those two surfaces is $2x^2+y^2=1$, so I get the parametric equation $\alpha(t)=(\frac{1}{\sqrt2}\cos(t), \sin(t))$ with $t \in [0, 2\pi]$.

And I choose the field $X(x,y)=(0,x)$ such that $Q_x-P_y=0$, where $Q=x$ and $P=0$

So, by Green's theorem: $A(S)=\int\int _{S} dA = \int _{0} ^{2\pi} X(\alpha(t)) \cdot \alpha'(t) dt=\frac{1}{\sqrt2}\int _{0} ^{2\pi} \cos^2(t)dt=\frac{\pi}{\sqrt2}$, which is incorrect

The correct answer is $\frac{\sqrt3\pi}{\sqrt2}$

答:
This is surface of the plane $x-y-z=1$ inside the elliptic cylinder $\frac{x^2}{(1/\sqrt2)^2} + \frac{y^2}{1^2} = 1$ $\, (a = \frac{1}{\sqrt2}, b = 1)$.

What you are doing is parametrizing your surface to find its area. I am not sure why you called you were applying Green's theorem. The part you missed was parametrizing your plane.

Parametrization of the plane is $z = f(x,y) = x-y - 1$.

$\frac{\partial f}{\partial x} = 1, \frac{\partial f}{\partial y} = -1$

$\sqrt{1+( \frac{\partial f}{\partial x})^2 + (\frac{\partial f}{\partial y})^2} = \sqrt3$. This has to be part of your surface area integral. In this case, it is a constant so you can multiply it after your integral.

So the desired surface area $= \sqrt{3} \times A \,$ where $A$ is the area of the ellipse in $XY$ plane. You already calculated $A$ correctly.

Or we also know that area of ellipse is given by $A = \pi \, a \, b = \frac{\pi}{\sqrt2}$


问:
What is the intuition for knowing when a fundamental group is trivial?
I'm studying fundamental groups in Kosniowski's First Course in Algebraic Topology, and I'm really having trouble understanding why fundamental groups are not always trivial. I have taken a knot theory class in the past, which I think is messing with me now, because in my mind every loop based at the same point is equivalent.

My professor has explained to me that on something like a torus, the hole in the center interrupts the action of "pulling" the loop in, so you end up with at least two equivalence classes (I think there should be three?). But in general, I don't really understand how to identify when a fundamental group is not trivial. And given a space like $X=\{a,b,c\}$ with topology $\{\emptyset, X, \{a\}\}$, where do I start with trying to understand the fundamental group, or is that question irrelevant without more information?

答:
Yes, a good way to think about it as having obstructions that don't let you pull your loop back into its basepoint. More rigorously, the following result holds:

Let $X$ be a topological space. $\pi_1(X, x_0)$ is trivial if and only if every loop $\gamma : S^1 \rightarrow X$ can be continuously extended into a function $f: B \rightarrow X$, where $B$ is the unit disk in $\mathbb{R}^2$.

Intuitively, this means that the fundamental group is trivial iff every loop can be "filled" up with a disk. The idea of filling up with a disk indicates some notion of nothing obstructing the interior of the shape drawn by the loop. In more exotic settings it doesn't necessarily have to be a hole which is causing this obstruction; for instance in $\mathbb{R}P^2$ it's more that you can't "pull back" into smaller circles sharing the same basepoint. This is different from a simple hole obstruction and indeed $\mathbb{R}P^2$'s fundamental group is of a different flavor as well (It is $\mathbb{Z}_2$). Here it's sort of like we can't pull the loop back in without "snapping" the "fabric" of the loop.

Later on, there will be better tools to understand and help you calculate the fundamental group such as covering spaces and van kampen theorem.


问:
Probability question involving three dice
Player $A$ rolls one die. Player $B$ rolls two dice. If $A$ rolls a number greater or equal to the largest number rolled by $B$, then $A$ wins, otherwise $B$ wins. What is the probability that $B$ wins?

I calculated the probability to be $$\frac 1 {36} + \frac 3 {36} \frac 5 6 + \frac 5  {36} \frac 4 6 + \frac 7 {36} \frac 3 6 + \frac 9 {36} \frac 2 6 + \frac {11} {36} \frac 1 6 = 1 -\frac {125} {216}$$

I then noticed that this is the same as $(5/6)^3$, and assumed that there might be a quicker way of obtaining this directly. Is this the case?

Body:
The probability is given by
$$
\sum_{k=1}^6P[\max(B_1,B_2)>k\mid A=k]\cdot P[A=k]
=
\tfrac16\Bigl(\tfrac{35}{36}
+\tfrac{34}{36}
+\tfrac{27}{36}
+\tfrac{20}{36}
+\tfrac{11}{36}
+\tfrac{0}{36}\Bigr)
=\tfrac{127}{216}
\approx0.587963.
$$


问:
Unique definition for analytic components of a function defined in an annulus
In his book "Complex Analysis" (5.1.3), when talking about Laurent series, Ahlfors' shows that a complex function $f(z)$, which is analytic in an annulus $R_1 < |z-a| < R_2$, can be always written as a

[...] sum $f_1(z) + f_2(z)$ where $f_1$ is analytic for $|z-a|<R_2$ and $f_2$ is analytic for $|z-a|>R_1$ with a removable singularity at $\infty$.

where

$$f_1(z) = \frac{1}{2\pi i} \int_{|\zeta-a|=r} \frac{f(\zeta) d\zeta}{\zeta-z} \text{ for $|z-a| < r < R_2$ } $$

$$f_2(z) = - \frac{1}{2\pi i} \int_{|\zeta - a|=r} \frac{f(\zeta)d\zeta}{\zeta-z} \text{ for $R_1 < r <|z-a|$}$$

Then, as the value of $r$ is "irrelevant as long as the inequality is fulfilled", $f_1$ and $f_2$ are uniquely defined and represent analytic functions in $|z-a|<R_2$ and $|z-a|>R_1$ respectively (see also this question and answers).

I am trying to understand what does it mean for $f_1$ and $f_2$ to be uniquely defined.
What if I take, for instance $f_3(z)=f_1(z)+z$ and $f_4(z)=f_2(z)-z$? It seems still true to me that $f_3(z) + f_4(z) = f(z)$ and $f_3(z)$ is analytic in $|z-a|<R_2$, while $f_4(z)$ seems analytic at $|z-a|>R_1$ (not sure what we can say at infinity, though; also, I don't see how I could write $-z$ as a sum of negative powers).

I am asking this also in light of what Penrose says in his book "The road to reality" (9.3), when (explaining frequency splitting on the Riemann sphere) he says:

We think of our splitting of $F(z)$ as expressing it as a sum of two parts, one of which extends holomorphically into the southern hemisphere—called the positive-frequency part of $F(z)$—as
defined by $F^\mathbf{+}(z)$, together with whatever portion of the constant term we choose to include, and the other, extending holomorphically into the northern hemisphere—called the negative-frequency part of $F(z)$ as defined by $F^\mathbf{-}(z)$ and the remaining portion of the constant term. If we ignore the constant term, this splitting is uniquely determined by this holomorphicity requirement for the extension into one or other of the two hemispheres.

Here $F(z)$ is a function which is "holomorphic in some open region including the unit circle".

So, in this case, are $F^\mathbf{+}$ and $F^\mathbf{-}$ unique (apart from a constant term)? Is then $F^\mathbf{-}=f_1$ and $F^\mathbf{+}=f_2$?
Maybe this also stems from the uniqueness of the Laurent development of $F$ (exercise from Ahlfors, same section), but I am not able to see how.

Thanks and sorry for the silly (maybe) question!

答: The function $f_2$ has a removable singularity at $\infty$. This means that the limit $\lim_{z\to\infty}f_2(z)$ exists (in $\Bbb C$). If $f_4(z)=f_2(z)-z$, then it is not true that $\lim_{z\to\infty}f_4(z)$ exists (again, in $\Bbb C$).


问:
Evaluating the series $\sum_{n=1}^{\infty} \frac{n}{e^{2 \pi n}-1}$ using the inverse Mellin transform
Inspired by this answer, I'm trying to show that $$\sum_{n=1}^{\infty} \frac{n}{e^{2 \pi n}-1} = \frac{1}{24} - \frac{1}{8 \pi}$$ using the inverse Mellin transform.

But the answer I get is twice as much as it should be, and I don't understand why.

EDIT:

With Marko Riedel's help, I corrected the error in my evaluation.

Since
$$ \left\{ \mathcal{M} \ \frac{x}{e^{2\pi x}-1} \right\}(s) = \int_{0}^{\infty} \frac{x^{s}}{e^{2 \pi x}-1} \, dx = (2\pi)^{-(s+1)}\Gamma(s+1)\zeta(s+1) $$ for $\operatorname{Re}(s) >1$,

we have
$$  \frac{x}{e^{2\pi x}-1}=\frac{1}{2\pi i}\int_{c-i\infty}^{c+i\infty}(2\pi)^{-(s+1)}\Gamma(s+1)\zeta(s+1) x^{-s} \, ds , $$ where $c >1$.

Replacing $x$ with $n$ and summing both sides, we get $$ \begin{align} \sum_{n=1}^{\infty}\frac{n}{e^{2\pi n}-1} &= \frac{1}{2\pi i}\int_{c-i\infty}^{c+i\infty}(2\pi)^{-(s+1)}\Gamma(s+1)\zeta(s+1)\zeta(s)\, ds \\&= \frac{1}{2 \pi i} \int_{c-i\infty}^{c+i\infty} f(s) \, ds. \end{align} $$

The integrand has simple poles at $s=-1, 0$, and $1$.

The fact that $\left|\Gamma(s)\right|$ decays exponentially fast to $0$ as $\text{Im} (s) \to \pm \infty$ allows us to shift the contour to the left.

I originally shifted the contour all the way to negative infinity.

But as Marko Riedel explains below, we want to shift the contour to the imaginary axis since the integrand is odd there.

Indeed, using the functional equation of the Riemann zeta function, we get $$ f(it) = \frac{it}{2 \pi} \sinh \left(\frac{\pi t }{2} \right) \operatorname{csch}(\pi t) \left|\zeta(1+it)\right|^{2}, \quad t \in \mathbb{R}.$$

Therefore,

$$ \int_{c-i \infty}^{c+i \infty} f(s) \, ds = 2 \pi i \ \text{Res}[f,1] + \pi i \ \text{Res}[f,0] ,$$

where

$$ \begin{align} \text{Res}[f,0] &= \lim_{s \to 0} s (2 \pi)^{-(s+1)} \Gamma(s+1) \zeta(s+1) \zeta(s) \\ &= \lim_{s\to 0} s\zeta(s+1) (2\pi)^{-(s+1)}\Gamma(s+1)\zeta(s) \\ &= 1\left(\frac{1}{2 \pi} \right)(1)\left(- \frac{1}{2} \right) \\ &=-\frac{1}{4 \pi} \end{align} $$

and

$$ \begin{align} \text{Res}[f,1] &= \lim_{s \to 1} (s-1) (2 \pi)^{-(s+1)} \Gamma(s+1) \zeta(s+1) \zeta(s) \\ &= \lim_{s\to 1}(s-1)\zeta(s) (2\pi)^{-(s+1)}\Gamma(s+1)\zeta(s+1) \\&= 1\left(\frac{1}{4 \pi^{2}}\right)(1)\left(\frac{\pi^{2}}{6}\right) \\ &=\frac{1}{24} . \end{align} $$

The result then follows.

答:
In response to your query on the other thread -- I don't have the time to typeset this properly, here are some comments. The effort looks good and you should keep working on it.

Don't extract any terms out from the transform function in front of the integral. As you have noticed yourself these reappear later on in the computation, reducing readability.

Now this is the important part -- when evaluating harmonic sums you get an asymptotic expansion about zero when shifting to the left and about infinity when shifting to the right. So it is no surprise that you do not get the right value -- the expansion does not converge there (at $x=1$).

With $g(s)$ being the transform of your sum we have
$$ g(s) =  \left( 2\,\pi  \right) ^{-s-1}\Gamma  \left( s+1 \right) \zeta
 \left( s+1 \right) \zeta  \left( s \right).$$
The residues are
$$\operatorname{Res}(g(s)/x^s; s=1) = \frac{1}{24x},$$
$$\operatorname{Res}(g(s)/x^s; s=0) = -\frac{1}{4\pi},$$
$$\operatorname{Res}(g(s)/x^s; s=-1) = \frac{x}{24}.$$
Now I suggest you shift from $\Re(s)=3/2$ to $\Re(s)=0$, indenting around the pole at zero by making a half-circle of radius $\epsilon$ around said pole at $s=0.$ This only picks up half the residue, so that your result is
$$\frac{1}{24\times 1} + \frac{1}{2}\left(-\frac{1}{4\pi} \right) =
\frac{1}{24} - \frac{1}{8\pi}.$$
You still need to verify that $g(s)$ is odd on the imaginary axis when $x=1$ by simplifying with the functional equation of the Riemann Zeta function.

That is all for now. I hope there are no mistakes.


问:
How to solve an optimization problems of this kind?
I have to solve a real-world optimization problem. I am teaching 33 students, a university lesson, and I am attempting to assign them 11 semester projects, based on their preference. I grouped them in 11 teams of 3 students per team, and asked them to state their 3 most preferenced projects.

Let student groups be $X_i , \text{where } i \in [1,11]$ and semester projects be $Y_i , \text{where } i \in [1,11]$

$X_1 \text{ chose in order of priority the projects } Y_7, Y_1, Y_10$

$X_2 \text{ chose in order of priority the projects } Y_2, Y_7, Y_6$

$... etc ...$

For simplicity's shake I will map this onto a matrix (columns = assignments, rows = groups, values = preferences)

\begin{matrix}
 2 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 3 & 0\\
 0 & 1 & 0 & 0 & 0 & 3 & 2 & 0 & 0 & 0 & 0\\
 0 & 0 & 0 & 2 & 0 & 0 & 3 & 0 & 0 & 0 & 1\\
 0 & 0 & 0 & 1 & 0 & 3 & 2 & 0 & 0 & 0 & 0\\
 3 & 0 & 0 & 0 & 1 & 2 & 0 & 0 & 0 & 0 & 0\\
 0 & 2 & 0 & 0 & 0 & 1 & 0 & 0 & 3 & 0 & 0\\
 0 & 0 & 0 & 0 & 2 & 0 & 1 & 0 & 0 & 0 & 2\\
 0 & 0 & 0 & 0 & 0 & 2 & 0 & 1 & 3 & 0 & 0\\
 0 & 0 & 0 & 0 & 0 & 3 & 0 & 1 & 2 & 0 & 0\\
 0 & 1 & 0 & 0 & 0 & 0 & 2 & 3 & 0 & 0 & 0\\
 0 & 0 & 0 & 0 & 1 & 3 & 0 & 0 & 0 & 0 & 2\\
\end{matrix}

This is an integer programming problem (I think?). How can this problem be solved? Is there an algorithm for that kind of optimization problems? I am missing knowledge here.

答: Take a look at the (balanced) assignment problem, which is what you probably have here (assuming you choose a suitable objective function, per LinAlg's comment).</p>


答:
Update: Sorry I didn't read carefully. You want the probability that $B$ wins, so it is indeed $\frac{125}{216}$, even though your equation gives $\frac{91}{216}$. Except for that, my analysis is correct. And yes you get your answer faster via $1-\frac{\sum_{j=1}^6 j^2}{216}=\frac{125}{216}$, but not from $\left(\frac 56\right)^3$.

Not sure how you arrived at $125$ since your equation gives $91$.

But, interestingly, $216-91=125$. Is it just a coincidence?

If Player $A$ throws a $j$, then there are $j^2$ cases that Player $B$ throws twice less than or equal to that, therefore the probability you want is $\frac{\sum_j j^2}{6^3} = \frac{91}{216}$, and you happen to have $6^3-\sum_{j=1}^6 j^2=125$. If you change 6 to some other integers you don't always get a perfect cube.

$3^3-\sum_{j=1}^3 j^2=13;$

$4^3-\sum_{j=1}^4 j^2=34;$

$5^3-\sum_{j=1}^3 j^2=70$, etc.

In general $n^3-\frac 16 n(n+1)(2n+1)=\frac 16 n(4n+1)(n-1)$ and you are lucky to have $4\cdot 6+1=25=(6-1)^2$.

(BTW if $n=14$ you get 1729, the taxicab number.)

Title: Probability question involving three dice

Body:
Player $A$ rolls one die. Player $B$ rolls two dice. If $A$ rolls a number greater or equal to the largest number rolled by $B$, then $A$ wins, otherwise $B$ wins. What is the probability that $B$ wins?

I calculated the probability to be $$\frac 1 {36} + \frac 3 {36} \frac 5 6 + \frac 5  {36} \frac 4 6 + \frac 7 {36} \frac 3 6 + \frac 9 {36} \frac 2 6 + \frac {11} {36} \frac 1 6 = 1 -\frac {125} {216}$$

I then noticed that this is the same as $(5/6)^3$, and assumed that there might be a quicker way of obtaining this directly. Is this the case?


问:
Is the quotient of a complete Heyting algebra by a prime filter complete?
Suppose $\mathbf A$ is a complete Heyting algebra and $F$ is a prime filter on $\mathbf A$. Do we then have that the quotient $\mathbf{A}/F$ is complete?

I have tried to prove this, but in my proof I needed that the filter $F$ fulfills
$$X\subseteq F\text{ implies }\bigwedge X\in F.$$

So one way of proving would be to show that any prime filter of a complete Heyting algebra has that property but I am not sure of that.

答:
No.  Suppose $\mathbf{A}$ is the lattice of open sets in some topological space $X$.  Then for each $x\in X$, the filter $F$ of open sets containing $x$ is prime, and the quotient $\mathbf{A}/F$ can be identified with the lattice of germs of open sets at $x$ (i.e., the colimit of the lattices of open subsets of $U$ where $U$ ranges over all neighborhoods of $x$).

In particular, let $X=\mathbb{N}\cup\{\infty\}$ and $x=\infty$.  Then the elements of $\mathbf{A}/F$ besides $1$ can be identified with the quotient of the Boolean algebra $\mathcal{P}(\mathbb{N})$ by the ideal of finite sets (an element of $\mathbf{A}/F$ besides $1$ is a germ of an open set that doesn't contain $\infty$, and that's just a subset of $\mathbb{N}$; two such subsets agree on a neighborhood of $\infty$ iff they differ by a finite set).  That is, $\mathbf{A}/F$ is the lattice $\mathcal{P}(\mathbb{N})/\mathrm{fin}$ with a greatest element added on top.  Since $\mathcal{P}(\mathbb{N})/\mathrm{fin}$ is not complete, neither is $\mathbf{A}/F$.

(Note that it is easier to come up with prime filters that are not closed under arbitrary joins--for instance, take a nonprincipal ultrafilter in $\mathcal{P}(\mathbb{N})$, or consider the case where $\mathbf{A}$ is totally ordered.  However, in those easy examples the quotient $\mathbf{A}/F$ is actually still complete!)


问:
$ \lim\limits_{n \to \infty} \| x_{n}\| = \| x \|$ if $\left(x_{n}\right)$ weakly convergent
I want to show that for a banach space $X, U \subset X$ non-empty and compact and $\left(x_{n}\right) \subset U$ a weakly convergent sequence with limit $x$, it converges in norm to $\mathrm{x}$

We know that  $\quad f\left(x_{n}\right) \rightarrow f(x) \: \:  \forall f \in X’$.

So

$$ \| x \| = sup_{\| f \| = 1} \| f(x) \| \\
 = sup_{\| f \| = 1} \lim\limits_{n \to \infty}  \| f(x_{n}) \| \\
= \lim\limits_{n \to \infty}sup_{\| f \| = 1} \| f(x_{n}) \| \\
= \lim\limits_{n \to \infty}  \| x_{n}\|$$

However, is it valid that I can interchange the limit and supremum?

答:
Considering the two topological spaces $(U,\|{\cdot}\|)$ and $(U,w)$, we have that the former is compact and the latter is Hausdorff.  Since we know that the identity map
$$
(U,\|{\cdot}\|) \to (U,w)
$$
is continuous, it must therefore be a homeomorphism by a well know Theorem of General Topology.

Thus the weak- and norm-convergent sequences are the same.


问:
If $\{x_n\}_{n\in I_m}$ is a Cauchy sequence, then $lim\{x_n-x_{n+c}\}_{n\in I_m}=0$ $\forall c\in \mathbb{N}$
I'm trying to prove the following:

If $\{x_n\}_{n\in I_m}$ is a Cauchy sequence, then: a) $lim\{x_n-x_{n+c}\}_{n\in I_m}=0$ $\forall c\in \mathbb{N}$. b) Given $\varepsilon >0, \exists N \in I_m : x_n \in (x_N-\varepsilon, x_N+\varepsilon)$, except for a finite number of terms.

The definition I have for Cauchy Sequence is "Let $\{a_n\}_{n\in I_m}$ be a sequence, $\{a_n\}_{n\in I_m}$ is a Cauchy sequence if $\forall \varepsilon >0, \exists M_{\varepsilon} \in I_m: \forall n,s \in I_{M_\varepsilon}, |a_n -a_s|<\varepsilon$"

For a), what I've thought is that, using the definition of a Cauchy sequence, then, if $\{x_n\}_{n\in I_m}$ is a Cauchy sequence, given $\varepsilon >0, \exists N \in I_m : \forall n,s \in I_N, |x_n-x_s|<\varepsilon$.

Now, for $c\in \mathbb{N}$, notice that $0<c \Rightarrow n<n+c$ and we can see that $x_n< x_{n+c} $

From this, I'm not sure how to say that $lim\{x_n-x_{n+c}\}_{n\in I_m}=0$ $\forall c\in \mathbb{N}$.

For b), I don't even know how to start.

答:
I'm confused with your indexing notation with the $I_m$'s so let me just write the sequence as $\{x_n\}_{n \in \mathbb{N}}$ instead. I'll leave it to you rewrite it in your notation.

$(a)$ Fix any $c \in \mathbb{N}$. We'll show $lim_{n \rightarrow \infty} \space x_n - x_{n+c} = 0$. So pick any $\epsilon > 0$. By cauchy-ness of $\{x_n\}_{n \in \mathbb{N}}$, there is a $N$ such that for all $n, m \geq N$, $|x_n - x_m| = |0-(x_n-x_m)| < \epsilon$. So in particular for any $n > N$, obviously $n+c > N$ as well, so $|0 - (x_n - x_{n+c})| < \epsilon$. So this shows convergence. You basically got it in your post.

$(b)$ The idea is simply that for cauchy sequences, the points begin to cluster together after some time. So the statement is saying that the $x_n$ cluster in an interval $\epsilon$ small after some point. Of course there can be outliers, but only finitely many.

So pick any $\epsilon > 0$. Then again by definition, there is a $N > 0$ such that for all $n, m \geq N$, $|x_n - x_m| < \epsilon$. Well this is just another way of saying that $x_n \in (x_m - \epsilon, x_m + \epsilon)$ .Well now let $m = N$. This means that for any $n \geq N$, we have that $x_n \in (x_N - \epsilon, x_N + \epsilon)$. Ok so we know that past a certain point, i.e, for all $n \geq N$, we have what we desire: $x_n \in (x_N - \epsilon, x_N + \epsilon)$. The only place left where this property can fail then is in the range of $0 \leq n < N$. But this is a finite range. So even if we have that $x_n \not \in (x_N - \epsilon, x_N + \epsilon)$ for EVERY $n < N$, that's still just finitely ($N$ many) violations. And we know that past $N$, we do have $x_n \in (x_N - \epsilon, x_N + \epsilon)$, so that means we can only really have finitely many violations (in fact we can only have up to $N$ many violations).


问:
The area of a square with length $\pi$ is $\pi^2$ by definition?

Area is the quantity that expresses the extent of a two-dimensional figure or shape or planar lamina, in the plane. When its sides have lengths of irrational numbers, are their areas defined, for example, the area of a square with length $\pi$ is $\pi^2$ by definition?

答:
I'm not sure if I'm reading the question correctly, but I think my answer sufficiently general to cover the likely interpretations.

I'd say it's a corollary of the definition of the area. A definition wouldn't give a particular value since it's establishing a general concept. Given what an area is, there is the particular way the concept applies to a square, which includes a relationship between the side length of a square and its area. Then, given some side length, we can deduce the area. So we have the definition, then from there a general formula for a square, then finally the specific case of a square with a given side length.

So the area of a square having side length $\pi$ is not $\pi^2$ strictly by definition. This isn' t to say the area isn't $\pi^2$, but rather this isn't strictly a fundamental statement of the meaning of a base level term, i.e. a definition.

Whether we are permitted an irrational value for the area depends on the fundamental definition of the area and not specific values.

Since it is a given that we are allowed irrational lengths, specifically $\pi$ and we have some concept of area, at minimum, what do we need to have an area with an irrational value?

If we have a rectangle of side lengths 1m and $\pi^2$m, do we have an rea of $\pi^2m^2$?

We have no real lengths without a definition of the reals, often defined as the ordered field having rationals as a subset and which satisfies the least upper bound property. This in turn implies density of the rationals in the reals (by way of the Archimedean property). So if we have arbitrary rational lengths and areas, then we have arbitrary real areas by the least upper bound property.

So depending on our definitions, but not by definition, we can prove the area of a square of side length $\pi$ is $\pi^2$.


问:
How to improve mathematical creativity?
To introduce myself: I'm an undergraduate mathematics student in Germany. Currently I'm studying in the second semester and until now I'm doing well, but I still got the feeling that my ability to develop proofs (or just solving complex issues in general) needs to be improved.

Let me explain myself: Sometimes, (especially) when it comes to proof tasks I'm being given, I feel like I dont know how to find my way through the proof, it rarely happens that I not even know where to start. Somehow I'm missing the feeling that my thoughts guide me to the correct answer, which I always used to have in school. This makes me feel a lack of "creativity" or in other words the ability to find my own path to reaching the solution.

If there is any advice you could give me, I would appreciate that.

答:
I remember having a similar feeling in my first undergraduate year. I could comprehend the proofs I was taught, and could mimic them afterwards on very similar problems, but I felt I lacked the creativity to actually think of proofs myself. Two realizations I had helped me get through this stage:

Practice actually helps. The more you prove, the more tools are added to your inventory, even if this is not immediately apparent. In two years from now, you'll look back and may not even understand what you found difficult.

Each of these proof "tools" was developed by someone very smart, generally over long periods of time thinking about the problems at hand. If you managed to come up with all the tricks and techniques by yourself, without first seeing some similar examples online or in books, you would indeed be a genius.

In short, you shouldn't be feeling too bad about not "getting" proofs immediately - this does not mean you aren't creative, just that you have more to learn and that things that are presented as trivial actually took quite a while to get to. One could almost say that this is what university is for - to save you the time it would take to reinvent everything yourself.

Title: How to improve mathematical creativity?


答:
There exist $n_0$ such that $|x_i-x_j| <\epsilon$  $\cdots   (1)$ if $i,j \geq n_0$ and $i,j \geq m$. Let $N$ be the maximum of $n_0$ and $m$. Then $|x_n-x_{n+c}| <\epsilon$ for $n \geq N$ (and any positive integer $c$).

We already have $x_n \in (x_N-\epsilon,x_N+\epsilon)$ if $n \geq N$ by (1). [Take $i=N$ and $j=n$].

Title: If $\{x_n\}_{n\in I_m}$ is a Cauchy sequence, then $lim\{x_n-x_{n+c}\}_{n\in I_m}=0$ $\forall c\in \mathbb{N}$

Body:
I'm trying to prove the following:

If $\{x_n\}_{n\in I_m}$ is a Cauchy sequence, then: a) $lim\{x_n-x_{n+c}\}_{n\in I_m}=0$ $\forall c\in \mathbb{N}$. b) Given $\varepsilon >0, \exists N \in I_m : x_n \in (x_N-\varepsilon, x_N+\varepsilon)$, except for a finite number of terms.

The definition I have for Cauchy Sequence is "Let $\{a_n\}_{n\in I_m}$ be a sequence, $\{a_n\}_{n\in I_m}$ is a Cauchy sequence if $\forall \varepsilon >0, \exists M_{\varepsilon} \in I_m: \forall n,s \in I_{M_\varepsilon}, |a_n -a_s|<\varepsilon$"

For a), what I've thought is that, using the definition of a Cauchy sequence, then, if $\{x_n\}_{n\in I_m}$ is a Cauchy sequence, given $\varepsilon >0, \exists N \in I_m : \forall n,s \in I_N, |x_n-x_s|<\varepsilon$.

Now, for $c\in \mathbb{N}$, notice that $0<c \Rightarrow n<n+c$ and we can see that $x_n< x_{n+c} $

From this, I'm not sure how to say that $lim\{x_n-x_{n+c}\}_{n\in I_m}=0$ $\forall c\in \mathbb{N}$.

For b), I don't even know how to start.


问:
Haar measure- $T-$ invariant
Let $\mathscr{G}=(G,\mathcal{B},\mu,T)$ be a measure-preserving dynamical system, and let $G$ be a locally compact topological group.

Let $(G,*)=\mathbb{R}/\mathbb{Z}$, and let $T:G\rightarrow G$, $T(r)=2r=r+r$$($mod $1)$.

Let $m$ be the Haar measure on $G$.

Is $m$ $T-$invariant?

I tried to show it myself, but ran into a problem because the Haar measure is invariant under
multiplication, which means $+$.

And moreover, if the answer is yes, then Haar is unique?

答:
Yes, $m$ is $T$-invariant even though Lebesgue's measure on $\mathbb R$ is not invariant under the transformation $x\mapsto 2x$.  The reason is that, by definition,  $m$ is $T$-invariant iff
$$
  m(T^{-1}(E)) = m(E),
  $$
for every measurable set $E$,
and it so happens that, at least for all small enough arcs $A\subseteq G$, one has that  $T^{-1}(A)$ consist of two  arcs, each of which has half the length of $A$, and hence, together, they have the right measure.

Regarding uniqueness, it is a well known result that Haar measure is always unique (regardless of invariance by whatever transformations) up to scalar multiplication.

Title: Haar measure- $T-$ invariant


问:
Prove that if $f$ is continuous at $a$, then it is bounded in a neighborhood of $a$
I want to prove that

if $f: A \rightarrow \mathbb{R}$ is continuous at a point $a \in A$, where $A$ is a subset of $\mathbb{R}$, then there is a constant $M>0$ and a neighborhood $N(a)$ s.t. $|f(x)|\leq M$ for all $x \in N(a)\cap A$.

答: From the definition of continuous function, there is a $\delta>0$ such that if $x\in A\cap\left(a-\delta,a+\delta\right)$ then $|f(x)-f(a)|<1$, hence $f(a)-1<f(x)<f(a)+1$ and $|f(x)|<\max\left\{|f(a)-1|,|f(a)+1|\right\}$. We can choose $N(a)=\left(a-\delta,a+\delta\right)$


答:
I think it is valid to question, whether a rectangle with (potentially) irrational sides $a$ and $b$ should have area $ab$.

The reason why this makes sense to me is that the product is a continuous function $\Bbb R \times \Bbb R \rightarrow \Bbb R$. So given any approximation $(a_n,b_n)_n$ of the rectangle by rectangles with rational sides, their areas will converge to the product $ab$. Hence it makes complete sense (or better is the only logical way) to define the area of a general rectangle to have area given by the product of its sides.

Title: The area of a square with length $\pi$ is $\pi^2$ by definition?

Body: Area is the quantity that expresses the extent of a two-dimensional figure or shape or planar lamina, in the plane. When its sides have lengths of irrational numbers, are their areas defined, for example, the area of a square with length $\pi$ is $\pi^2$ by definition?


问:
Rings without identity and non-isomorphic ring structure on $\mathbb{Z}$
I am solving Exercise 2.15 from Aluffi chapter 0.

Exercise 2.15. For $m > 0$ , the abelian group $(\mathbb{Z},+)$ and $(m\mathbb{Z},+)$ are manifestly isomorphic: the function $\phi : \mathbb{Z} \rightarrow m\mathbb{Z}$ given by $n \mapsto nm$ is a group isomorphism. Use this isomorphism to transfer the structure of "ring without identity" $(m\mathbb{Z},+,*)$ back onto $\mathbb{Z}$: Give an explicit formula for the "multiplication" this defines on $\mathbb{Z}$. Explain why structures induced by different positive integer m are non-isomorphic as "rings without 1".

Solution:

We have the following map:

$\phi : \mathbb{Z} \rightarrow m\mathbb{Z}$ given by $n \mapsto nm$. We can use this map to transfer ring structure on $\mathbb{Z}$ as follows:

Let $s_1,s_2 \in \mathbb{Z}$ and set $s_1 s_2 = m (s_1 s_2)$. This defines ring structure on $\mathbb{Z}$. This ring structure is non-isomorphic because if we have $s_1 s_2 = m (s_1 s_2) = n (s_1 s_2)$ then we would have n = m for $n \neq m$. Is my my argument valid ?

答:
Also note that by distributivity a non-unital ring structure on the group $(\Bbb{Z},+)$ is determined by $1 \times 1$. For each $n\in \Bbb{Z}$ there is a non-unital ring structure $(\Bbb{Z},+,\times)$ $$a\times b = abn$$ and all the non-unital ring structures are of this form.

For $n\ne 0$ it embeds into the standard ring $\Bbb{Z}$ through $a\to an$.

For any $n$ it embeds into the unitalization $\Bbb{Z}[x]/(x^2-nx)$.


答:
Three dice are rolled.  $A$ wins if his roll is the largest (or tied for largest).  There are three cases: (a) all three rolls are different, (b) two rolls are the same and the third is different, and (c) all three rolls are the same.  Case (a) can happen in $6\cdot 5\cdot 4$ ways, and $A$ wins with probability $1/3$ in that case.  Case (c) can happen in $6$ ways, and $A$ definitely wins in that case.  Finally, case (b) can happen in $6\cdot 5\cdot 3$ ways... in half of these, the pair is larger than the singleton, and $A$ wins with probability $2/3$; in the rest, the pair is smaller than the singleton, and $A$ wins with probability $1/3$... so overall, $A$ wins with probability $1/2$ in case (b).

The result is

$$
P_A=\frac{(6\cdot 5\cdot 4) \cdot \frac{1}{3}+(6\cdot 5\cdot 3)\cdot\frac{1}{2}+6}{6^3}=\frac{40+45+6}{6^3}=\frac{91}{216}.
$$


答: If $f(a) \neq 0$, we can take $\varepsilon = |f(a)|/2 > 0$ in the definition of continuity. There is $\delta > 0$ such that for all $x \in (a-\delta, a+\delta)$, $|f(x)-f(a)| \leq |f(a)|/2$. This last inequality can be rewritten as $$\frac{|f(a)|}{2} < f(x) < \frac{3|f(a)|}{2}.$$

Title: Prove that if $f$ is continuous at $a$, then it is bounded in a neighborhood of $a$

Body:
I want to prove that

if $f: A \rightarrow \mathbb{R}$ is continuous at a point $a \in A$, where $A$ is a subset of $\mathbb{R}$, then there is a constant $M>0$ and a neighborhood $N(a)$ s.t. $|f(x)|\leq M$ for all $x \in N(a)\cap A$.


问:
What is the intuitive motivation for defining equivalence relations with the properties of reflexivity, symmetry, and transitivity?
I am trying to understand why equivalence relations are defined using the three properties of reflexivity, symmetry, and transitivity.

Using an example set of $S = \{1,2,3,4,5,6,7,8,9\}$

It seems to me like a good first intuition is the following:

Reflexive

An equivalence relation's reflexive property basically ensures that every element in the set under examination can be partitioned (i.e. occupy its own equivalence class).

For example, if we had $R_1$ be a relation on $S$ defined as $x-y$ is divisible by $10$, then, because $(1,1)$ , $(2,2)$ , $(3,3)$ , $etc$ are order pairs that will all satisfy $R_1$, we will end up with 10 different equivalence classes ($e.g. [1],[2],[3], etc)$. Therefore, all elements are partitioned...which makes sense because each of these elements $mod(10)$ have a unique remainder...namely $1$, $2$, $3$, $etc$

Transitive

An equivalence relation's transitive property basically allows you to "unidirectionally" (my meaning will be understood shortly) link all elements belonging to the same equivalence class.

For example, if we had $R_2$ be a relation on $S$ defined as $x-y$ is divisible by $2$, then the following ordered pairs (non-exhaustive) are certainly in the set: $(2,4)$, $(4,6)$, $(6,8)$. Pretend I do not know any other ordered pairs.

Now, if I choose as my representative element $[2]$, I can build my equivalence class by starting with $2\ R_2\ n$. Well, $(2,4)$ is in $R_2$ therefore, $4$ belongs to the same equivalence class as $2$. What works with $4\ R_2\ n$? Well $(4,6)$  is in $R_2$ and therefore $6$ is in the same equivalence class as $2$ and $4$.

However, let's say that I start with $[8]$ instead of $[2]$. Which of the elements in set $S$ are in the same equivalence class? Namely, for which value of $n$ is $8\ R_2\ n$ true? Well, I know I have the ordered pair $(6,8)$...but that is not the same form as $8\ R_2\ 6$. If only I knew that $(8,6)$ was also in the set describing $R_2$...and this is where symmetry comes into play.

Symmetric

An equivalence relation's symmetry property, in conjunction with the transitive property, allows you to bidirectionally link all elements belonging to an equivalence class (regardless of which 'starting element' you choose to represent your equivalence class).

For example, incorporating the symmetry property with the above transitivity example, I now know that if $(2,4)$, $(4,6)$, and $(6,8)$ are in my $R_2$ set, then I also know that $(4,2)$,$(6,4)$, and $(8,6)$ are in my $R_2$ set. Consequently, if someone asks me what are the other elements that belong to $[8]$, without hesitation I can say $2$,$4$, and $6$.

Are these the correct ways (at a very basic level) of intuitively understanding the motivation behind using these 3 properties to define equivalence relations?

答:
Say $ M $ is a set and $ \sim $ is a relation on it ( Recall that a relation $ R $ on a set $ S $ is simply a subset $ R \subseteq S \times S $, and that $ (a,b) \in R $ is also written as $ aRb $ ). Now $ \sim $ immediately gives rise to a collection $ C  := \{ [x] : x \in M \} $ of subsets of $ M $, where $ [x] := \{ y \in M : x \sim y \} $.

In general the collection $ C $ has no specific structure. We can ask ourselves the following question :
Under what kinds of $ \sim $ do we get that $ C $ is a partition of $ M $, and that " $ \sim $ can be naturally reconstructed from knowing the set $ C $ alone " i.e. $ \sim  =  \sim' $ where $ a \sim' b \stackrel{\text{def}}{\iff} ( a, b \text{ belong to same element of } C ) $ ?

[ By the way recall a partition of a set $ S $ is just a collection of pairwise disjoint non-empty sets whose union is $ S $ ]

It's clear any such $ \sim $ should be reflexive, symmetric and transitive, i.e. reflexive symmetric transitive relations (on $ M $) are the only potential candidates for $ \sim $ . Turns out any reflexive symmetric transitive relation will do : Let $ R $ be a reflexive symmetric transitive relation on $ M $. This gives a collection $ C $ of classes $ [x] = \{ y \in M : xRy \} $. As $ x \in [x] $, elements of $ C $ are non-empty and have union $ M $. From symmetry and transitivity of $ R $ we get that "If $ [x] \cap [y] \neq \phi $, then $ [x] = [y] $", i.e. that elements of $ C $ are pairwise-disjoint. Also $ R = R' $ where $ aR'b \stackrel{\text{def}}{\iff} ( a, b \text{ belong to same element of } C ) $.

Hence our question is settled, relations which are reflexive symmetric and transitive are precisely the ones we were looking for. These are also called "equivalence relations".

Edit : Saying "$\sim$ is equal to the natural grouping relation arising from $C$" instead of "$\sim$ can be naturally reconstructed from knowing $C$ alone", as pointed out in the comments, would've been more appropriate.


问:
Divide by a number without dividing.
Can anyone come up with a way to divide any given x by any given y without actually dividing?

For example to add any given x to any given y without adding you would just do:

$x-(-y)$

And to subtract any given x from any given y (that is, y-x) you could do:

$y+xe^{iπ}$

*edit: well since (i) is ($\sqrt{-1}$) and that is technically subtracting this one might not work perfectly but for the sake of the riddle and for the sake of example, I'm using that equation :)

How can you divide without dividing? Can anyone come up with equations that work for all $x$ and $y$ values? (For all intents and purposes we will leave out dividing by zero issues and what-not... don't worry about that...

答:
Logs turn reciprocals into minus signs: $\ln(1/y)=-\ln(y)$.  Thus, $$x/y=xe^{-\ln y}.$$

(This is assuming that $y$ is positive.  If $y$ is negative, then $x/y=-xe^{-\ln(-y)}$.)

Title: Divide by a number without dividing.


问:
How to justify dropping the absolute value when taking the derivative of secant?
Shown are two different methods for finding $du$ when $u=\frac{1}{2}sec(v)$. I'm failing to see how we are able to justify dropping the absolute value sign in the second method. Thanks!

答:
The first method gives you the correct derivative for all $v$ where $\sec v$ is defined.

The second method, as written, is only applicable to $0\le v\le\pi$ (excluding $v=\pi/2$), but in this interval, $\sec v\tan v\ge 0$ anyways, and so the absolute value can be dropped.

However, in other intervals for $v$, the formula $v=\text{arcsec}(2u)$ will be incorrect, and a more sophisticated formula will be valid. E.g. for $\pi\le v\le 2\pi$, you would instead have this formula: $v=2\pi-\text{arcsec}(2u)$, and that minus sign (in front of $\text{arcsec}$) will cancel the absolute value, because, between $\pi$ and $2\pi$, we will have $\sec v\tan v\le 0$.

I would leave it to you to look at a few further intervals and convince yourself that the second method, when the $\text{arcsec}$ formula is corrected, always yields the same result as the first method.


问:
What are some examples of infinite strict quasigroups?
By strict quasigroup I mean a quasigroup with no identity. I've come across one so far in the answer to this question, but I can't seem to find any others. I am particularly interested in finding example of:

Infinite strict quasigroups that are idempotent

Infinite strict quasigroups with neither a left nor a right identity

Infinite strict quasigroups that are idempotent and have neither a left nor a right identity

But other examples "interesting" infinite strict quasigroups are welcome!

答:
The midpoint (or mean) between two points in $\mathbb{R}^n$.

$(a+b)/2=b$ iff $a=b$.


问:
Find $M$, where $M^7=I$ and $M\neq I$, $M$ has only 0's and 1's.
Find a $3 \times 3 $ matrix $M$ with entries 0 and 1 only such that $M^7=I$ and $M\neq I$.

This was a short question in a recent exam. I tried with permutation matrices but couldn't find $M^{odd}=I$ except for 3.

答:
There is no such matrix over $\mathbb{R}$. The matrix satisfies the polynomial $x^7−1$ which implies that the eigenvalues lie amongst the $7^{\text{th}}$ roots of unity and that the matrix is diagonalizable. This implies that the characteristic polynomial, being a real cubic, has either three real roots, or one real root and a conjugate root pair.

If all roots are real then we must have $1$ repeated three times as the eigenvalues. Diagonalizability then forces $M=I$.

If we have a conjugate root pair, say $\left(\omega, \overline{\omega}\right)$ and a real root (which is again $1$) then we know that
$$1 + \omega + \overline{\omega} = 1 + 2\Re(\omega) = \mathrm{tr}(M)$$
But since $M$ has only $0$s and $1$s as entries this implies that the trace is integral and hence $2\Re(\omega)$ is integral. It is easy to check that this is impossible.

If you allow other fields then this is possible. As julien points out, if we work over $\mathbb{Z}/7\mathbb{Z}$ then
$$M=\begin{pmatrix}1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}$$
is a working example.


问:
Given matrix $A$, decide the existence of a $k \times k$ matrix $X$ such that $X^n=A$
Let $R$ be a commutative ring with an identity element $1$. Is there a $k\times k$ matrix $X$ over $R$ such that
$$
X^n=
\overbrace{
\begin{pmatrix}
  1 & 1 & 0 & \cdots & 0\\
 -1 & -1 & 0 &\cdots & 0 \\
  0 & 0 & 0 & \ldots & 0 \\
  \vdots & \vdots & \vdots & \ddots & \vdots\\
  0 & 0 & 0 &\cdots & 0
\end{pmatrix}
}^{\mathrm{A}}\ ?
$$
If $k\leq n$, then the answer is no, since $A^2=O$, so $X^{2n}=O$. If the minimal polynomial of $X$ os $m(t)$, then $m(t)\mid t^{2n}$ and since $\deg m(t)\leq k$, it follows that $X^k=O$, so $X^n=O$, a contradiction. What can be said when $n<k$ ?

答:
Let

$J_m$ be the $m\times m$ (upper triangular) nilpotent Jordan block,

$E_{ij}$ be the matrix with a $1$ at the $(i,j)$-th position and zeroes elsewhere,

$P=P^{-1}$ be the permutation matrix for the transposition $\pmatrix{2&n+1}$, and

$S=\pmatrix{-1&-1\\ 1&0}$, with $S^{-1}=\pmatrix{0&1\\ -1&-1}$ also lies inside $M_k(R)$.

Then
\begin{aligned}
A&=\pmatrix{1&1\\ -1&-1}\oplus0_{(k-2)\times(k-2)}\\
&=\left(S\oplus I_{k-2}\right)\left(J_2\oplus0_{(k-2)\times(k-2)}\right)\left(S^{-1}\oplus I_{k-2}\right)\\
&=\left(S\oplus I_{k-2}\right)PE_{1,n+1}P^{-1}\left(S^{-1}\oplus I_{k-2}\right)\\
&=\left(S\oplus I_{k-2}\right)P\left(J_{n+1}^n\oplus0_{(k-n-1)\times(k-n-1)}\right)P^{-1}\left(S^{-1}\oplus I_{k-2}\right)\\
&=\left[\left(S\oplus I_{k-2}\right)P\left(J_{n+1}\oplus0_{(k-n-1)\times(k-n-1)}\right)P^{-1}\left(S^{-1}\oplus I_{k-2}\right)\right]^{\,n}.\\
\end{aligned}


问:
Fourier Transform of the Weierstrass Function
I'm looking to compute the Fourier Transform of the Weierstrass Function over the interval $[0,2\pi]$:
$$W(t) = \sum_{n=1}^\infty a^n \cos(b^n t) $$
where $0<a<1$, $b$ is a positive integer such that and $ab > 1+\frac{3\pi}{2}$.

In computing the integral
$$\int_0^{2\pi} \sum_{n=1}^{\infty} a^n\cos(b^nt)e^{2\pi i st}dt$$
I've tried writing $\cos(b^nt) = \frac{e^{ib^nt }+e^{-ib^nt}}{2}$. I use geometric series to get rid of the sum, but then I get the integral

$$\int_0^{2\pi} \frac{e^{2\pi i s t}}{2}e^{ibt} \left(\frac{1}{1/a-e^{ibt}} + \frac{1}{1/a-e^{-ibt}} \right)dt $$
which I don't know how to solve, even when I put it under a common demoninators and right the bracketed expression in terms of $\cos(bt)$.

I've also tried interchanging the sum and the integral. However, I get an unwiedly sum.

Is there a clever way of going about this or am I missing something in one of these methods.

答:
For $b$ an integer $\ne -1,0,1$ and $|a|<1$ then $$W(t)=\sum_{n=1}^\infty a^n \cos(b^n t)$$ is already a $2\pi$-periodic Fourier series and $$c_k=\frac1{2\pi}\int_0^{2\pi} W(t)e^{-ikt}dt = \cases{\frac12 a^{n} \ if \ |k| = |b|^n\\ 0 \ otherwise}$$
$$W(t)=\sum_{k=-\infty}^\infty c_k e^{ikt}$$


问:
Bounding a Function When We Only Know Its Dot Product Against Test Functions.
Let $\phi : \mathbb{R}^d\to  \mathbb{R}^d $ be in  $ C^{\infty}_0( \mathbb{R}^d)$ that is its continuously differentiable and has compact support. Take some other vector field $v: \mathbb{R}^d\to  \mathbb{R}^d$.

$\textbf{Question : }$ Is there any hope in bounding the (euclidean) norm $\|v(x)\|$ $\textbf{if}$ I have a bound on $  | v(x)\cdot \phi(x) |$  $\forall \phi  \in  C^{\infty}_0( \mathbb{R}^d)$ ?

答: Not with the current hypothesis.  If $d=1$ and $v(x)=x$, then $v$ is bounded on all compact sets, so $|v(x)\cdot\phi(x)|$ is always bounded, but of course $v$ is unbounded.


问:
How do you find the sum of this infinite series?
The actual series that I want to solve:
$$
\sum_{n=2}^{\infty}\frac{n 2^{n-1} + \frac{n(n-1)}{1\cdot 2}2^{n-2}+\frac{n(n-1)(n-2)}{1\cdot 2\cdot 3}2^{n-3}+\cdots+n 2^1+1}{3^n}
$$

Body:
Hint: Note that
$$(2+1)^n = 2^n + n 2^{n-1} + \binom{n}{2} 2^{n-2} + \binom{n}{3} 2^{n-3} + \cdots + n 2^1 + 1.$$


问:
how many integers as product of prime factors within 100?
Found a pretty challenging question.

How many integers from $2$ to $100$ can be expressed as the product of prime numbers $x$ and $y$ such that $x \leq y$ ?

It seems like a lot if I calculate by hand, anyone could tell a more convenient way to find it?

答:
Well by hand you would have to begin from the prime that is less or equal to $\sqrt{10}$, so 7.

So if $x=7$ then $y=7,11,13$ are the only ones.

if $x=5$, $y\in \{$ primes between $5$ and $17 \}$

if $x=3$, $y\in \{$ primes between $3$ and $31 \}$

if $x=2$, $y\in \{$ primes between $2$ and $47 \}$

So the answer may be $34$


答:
I don't think there's a significantly faster way to do it, but don't worry- blunt force actually isn't that bad here! We fix $x$ and let $y$ vary:

$x=2\implies 2\le y\le 47$

$x=3\implies 3\le y\le 31$

$x=5\implies 5\le y\le 19$

$x=7\implies 7\le y\le 13$

Otherwise, for $x\ge 11$, there is no solution for $y$.

So how many primes are there from $3$ to $47$, plus the number of primes from $5$ to $31$, plus ... et cetera? I'm sure you can do that by hand.

Title: how many integers as product of prime factors within 100?

Body:
Found a pretty challenging question.

How many integers from $2$ to $100$ can be expressed as the product of prime numbers $x$ and $y$ such that $x \leq y$ ?

It seems like a lot if I calculate by hand, anyone could tell a more convenient way to find it?


答:
Use binomial theorem to rewrite the numerator as
$$\sum_{k=1}^n \binom nk 2^{n-k} = \sum_{k=0}^n \binom nk 2^{n-k} - 2^n = (1+2)^n-2^n=3^n-2^n$$.

Title: How do you find the sum of this infinite series?

Body:
The actual series that I want to solve:
$$
\sum_{n=2}^{\infty}\frac{n 2^{n-1} + \frac{n(n-1)}{1\cdot 2}2^{n-2}+\frac{n(n-1)(n-2)}{1\cdot 2\cdot 3}2^{n-3}+\cdots+n 2^1+1}{3^n}
$$


答:
Look at the equation $\frac{1}{x}=a$. We use Newton's Method to approximate the solution.

Let $f(x)=\frac{1}{x}-a$. The standard Newton iteration gives
$$x_{n+1}=x_n -\frac{f(x_n)}{f'(x_n)}=x_n -\frac{\frac{1}{x_n}-a}{-\frac{1}{x_n^2}}.$$
This simplifies to
$$x_{n+1}=x_n(2-ax_n).$$

Remark: Note that only subtraction and multiplication are used. If we start with $x_0$ close enough to $\frac{1}{a}$, the method converges rapidly. It was once used to implement reciprocal in software.

Title: Divide by a number without dividing.

Body:
Can anyone come up with a way to divide any given x by any given y without actually dividing?

For example to add any given x to any given y without adding you would just do:

$x-(-y)$

And to subtract any given x from any given y (that is, y-x) you could do:

$y+xe^{iπ}$

*edit: well since (i) is ($\sqrt{-1}$) and that is technically subtracting this one might not work perfectly but for the sake of the riddle and for the sake of example, I'm using that equation :)

How can you divide without dividing? Can anyone come up with equations that work for all $x$ and $y$ values? (For all intents and purposes we will leave out dividing by zero issues and what-not... don't worry about that...


答:
I think counting by hand is the best option here. But we can be systematic about it.

It's clear that $x$ can be $2,3,5,7$, and nothing else (any other prime is too large).

If $x=7$, then $y$ is either $7, 11$ or $13$

If $x=5$, then $y$ can be anything from the above, or $5, 17$ or $19$

If $x=3$, then $y$ can be anything from the above, or $3, 23,29$ or $31$

If $x=2$, then $y$ can be anything from the above, or $2,37,41,43$ or $47$.

In total, we have $3+6+10+15=34$ possibilities.


问:
How to homogenize a general map?
I'm reading  Algebraic Geometry, A Problem Solving Approach, section 1.8.

(I put a picture of this page)

In the Exercise 1.7.3, we can give a map $\tilde{\psi}$ from $\mathbb{C}$ to the circle $V(x^2+y^2-1)\subset \mathbb{C}^2$, in fact, $\tilde{\psi}(\lambda)=\left(\frac{2\lambda}{\lambda^2+1}, \frac{\lambda^2-1}{\lambda^2+1}\right)$. I understand how this map is derived, and then it goes, ``to work in projective space, .... we have to homogenize our map''. I have no idea how to extend the map $\tilde{\psi}:\mathbb{C}\to V(x^2+y^2-1)\subset\mathbb{C}^2$ to

$$\psi:\mathbb{CP}^1\to \{(x:y:z)\in\mathbb{CP}^2: x^2+y^2-z^2=0\}$$

as $\psi(\lambda :\mu)=(2\lambda\mu:\lambda^2-\mu^2:\lambda^2+\mu^2)$.

I have already know that if $p(x,y)$ is a polynomial with highest sum degree $n$, then $z^np(x/z, y/z)$ will homogenize $p$. But could you help to give some explaination about how to homogenize a general rational map?  Or please give me some keywords to google.

答:
Start from
$$[\lambda:1]\to\left[\frac{2\lambda}{\lambda^2+1}: \frac{\lambda^2-1}{\lambda^2+1}:1\right]$$
Then replace $\lambda$ by $x/y$ to get

$$[x:y]=[x/y:1]\to\left[\frac{2x/y}{(x/y)^2+1}:\frac{(x/y)^2-1}{(x/y)^2+1}:1\right]=\left[2x/y:(x/y)^2-1:(x/y)^2+1\right]=\left[2xy, x^2-y^2:x^2+y^2\right]$$
If you are affraid by the poles and the zeros then $=$ is in the sense of rational maps.

Since always one of the terms is nonzero then
$$[x:y]\to \left[2xy: x^2-y^2:x^2+y^2\right]$$ is your globally defined morphism on the projective closures.

It is unclear if an arbitrary morphism of projective varieties will always be represented this way by a single homogeneous polynomial map not vanishing anywhere, that's why we deal with charts to define the morphism locally where it has to be given by some regular functions.

Title: How to homogenize a general map?


问:
Optimal solution to non-linear program
Find an optimal solution to the following problem:

$$\min_{x\in \mathbb{R}^n} \sum_{i=1}^{n}\frac{1}{2}(x_i-1)^2$$
$$\text{s.t. } x\ge0 \text{ and } \sum_{i=1}^{n}x_i=1.$$

答:
If we let $e=(1,...,1)$ the the problem becomes
$\min_{e^T x = 1, x \ge 0 } { 1\over 2} \|x-e\|^2$ which we can see is
projecting the point $e$ onto the simplex.

One nice characteristic of this problem is that it is convex, and first order conditions are necessary and sufficient.

One approach is to solve a more relaxed problem and if this is a solution then it solves the more constrained problem.

Solving $\min_{e^T x = 1 } { 1\over 2} \|x-e\|^2$ gives
$(x-e) + \lambda e = 0$, or $x=(1-\lambda) e$ and from the
constraint we have $e^T x = 1 = (1-\lambda) e^T e  = n (1-\lambda)$ and so
$(1-\lambda) = {1 \over n}$ which gives
$x = {1 \over n} e$. Since $x>0$ this solves the original problem.

Title: Optimal solution to non-linear program


问:
On the convergence of a real sequence satisfying certain conditions
Let $(x_n)$ be a real sequence and $\beta_n$ be any strictly increasing sequence of positive integers.

We say that $x_n\in D_{so}$, if
for all $\epsilon>0$ there exists $\delta=\delta(\epsilon)$ and $N=N(\epsilon)$ such that $\mid x_m-x_{\beta_n} \mid<\epsilon$ whenever $n\geq N(\epsilon)$ and $\beta_n< m\leq (1+\delta)\beta_n$.

I want to prove: If $x_n\in D_{so}$ and $(x_{\beta_n})$ is convergent to $L$, then $(x_n)$ is convergent to $L$.

I tried:

Firstly assume that $(x_{\beta_n})$ is convergent to $L$. Then for all $\epsilon>0$ there exists and $N_0=N_0(\epsilon)$ such that $\mid x_{\beta_n}-L \mid<\epsilon$ whenever $n\geq N_0(\epsilon)$.

Now, assume $x_n\in D_{so}$. Then for all $\epsilon>0$ there exists $\delta=\delta(\epsilon)$ and $N=N(\epsilon)$ such that $\mid x_m-x_{\beta_n} \mid<\epsilon$ whenever $n\geq N(\epsilon)$ and $\beta_n< m\leq (1+\delta)\beta_n$.

Put $M=\max\{N,N_0\}$. Then, for all $n\geq M$ and accordingly for all $m,\beta_n\geq M$ (since $\beta_n$ is as large as $n$), we have
$$\mid x_m-L \mid \leq \mid x_m-x_{\beta_n} \mid + \mid x_{\beta_n}-L \mid<\epsilon+\epsilon=2\epsilon.$$
Therefore, $(x_n)$ is convergent to $L$.

答:
This needn't be true.

Let $\beta_n=2^n$ and $x_n=0$ if $2^m\leq n\leq 1.5\times 2^m$ for some $m\geq 1$, $x_n=1$ otherwise.

Then note that for all $\epsilon >0$, with $\delta(\epsilon)=0.5$ and $N(\epsilon)=1$, if $n\geq N$, and $\beta_n\leq m\leq (1+\delta)\beta_n$, then by construction of the sequence, $|x_m-x_{\beta_n}|=|0-0|=0<\epsilon$. So $x_n\in D_{so}$ . Moreover, clearly $x_{\beta_n}=0$ for all $n$, so in particular $(x_{\beta_n})$ converges to $0$.

However, note that for all $n\geq 2$, $1.5\times 2^n = 2^n + 2^{n-1} < 2^n + 2^n - 1 = 2^{n+1}-1< 2^{n+1}$. So for all $n\geq 2$, $x_{2^{n+1}-1}=1$.

So $(x_n)$ does not converge to $0$.