问:
What set of formal rules can we use to safely apply Universal/Existential Generalizations and Specifications?
This question is mainly about formality, not intuition.

There are some questions here (and a lot of answers) about Universal Generalization. Each of these states some rules that can be used to avoid fallacies in a First Order Logic argument.

1: This post says:

Assume $\Gamma$ is a set of formulas, $\varphi$ a formula, and $\Gamma \vdash \varphi(y)$ has been derived.  The generalization rule states that $\Gamma \vdash \forall x \varphi(x)$ can be derived if $y$ is not mentioned in $\Gamma$ and $x$ does not occur in $\varphi$.

2: This other one says:

The following restrictions apply:

The term $t$ cannot occur in any undischarged assumption of the derivation of $\phi[t/x]$

The term $t$ cannot occur in $\phi$

3: An answer on the same question says:

$t=0$ --- assumption : is $\phi[t/x]$

$\forall x \ (x =0)$ --- from 1) by $\forall$I : wrong : $t$ is free in the one-line derivation of $\phi[t/x]$ , i.e. in $t=0$

4: One answer on this question says:

So, typically formalizations of the rule will say that $a$ needs to be a 'fresh' or 'new' constant: a constant that is not used elsewhere for a different purpose.

[...]

For Existential Elimination something similar happens. [...] In other words, once again you have to introduce a new constant.

From that, we can extract some rules that can be used (some of them are repeated, like "there can't be $x$ on the premise" and "there can't be $x$ anywhere before", in that case, we'll use the stronger version). For any substitution $P(a)$ to $\forall x[P(x)]$ (Universal Generalization) or $\exists y[P(y)]$ to $P(b)$ (Existential Instantiation):

$a$ can't have appeared in any undischarged assumptions/premises.

$a$ can't occur in $P$ after the substitution.

$x$ has to be a new variable.

$b$ has to be a new variable.

From this answer, it is clear that they are not meant to be used together:

Different systems define these rules a bit differently in terms of notation. For example, some systems simply drop quantifiers for the elimination rules, leaving what seems to be free variables in the formula, while others replace those variables with constant symbols. Either way, however, restrictions do indeed need to be in place that prevent you from making invalid inferences, as you already suspected.

A smaller combination of these seems to be usually regarded as enough, but for the sake of argument, let's use them all of them together. Now consider the following:
$$ \begin{align}\exists x[P(x)] & \quad \text{Premise} \\ P(a) & \quad \text{Existential Instantiation} \\ \forall y[P(y)] & \quad \text{Universal Generalization} \end{align} $$

It is clear that the above argument is a fallacy. If it works for one example, it doesn't mean it works for all of them. Still, all the rules were followed:

$a$ doesn't appear in the premise

$a$ doesn't occur after the substitution

$y$ is a new variable

$a$ is a new variable

Now of course, we can also add a new rule that states "If $a$ came from a Existential Instatiation, then it cannot be used in a Universal Generalization", but given that even following those 4 (quite strict) rules still resulted in a fallacy, what guarantees that there isn't some subtle example in which, even following those 5 rules, we'll still end up with a fallacy?

Almost all of these answers cite that "$a$ has to be arbitrary and not specific", or "we can't have previously assumed anything about $a$", but those are very informal and imprecise ways of stating how Universal Generalization can be safely used.

So, given that, my question is: What set of rules can one use, for which it is guaranteed that, given a statement $P(x)$, you can safely conclude that $\forall x[P(x)]$?

Edit: Though this question has been marked as a duplicate of Restrictions on the use of universal generalization, that question is asking how to understand these rules, and why they exist (also the case for this linked question), which is not the point of my question. It is clear to me how to use them (or so I hope, if I did not apply one of the rules properly, I'd be more than glad to be corrected). Also, it is clear why they exist, it's to avoid fallacies like the one presented above (namely, $ \exists x[P(x)] \Rightarrow P(a) \Rightarrow \forall y[P(y)]$). Now, even though that is their purpose, they don't seem to be strong enough to always avoid a fallacy. Even on an argument in which all of them are followed, it still leads to a conclusion that clearly shouldn't follow from the premise. So my question remains: Since these don't seem to be enough, which set of rules can be used to always avoid a fallacious use of UG?

Edit: Changed question from only Universal Generalization to Universal/Existential Generalizations and Specifications, to reflect evolving answers regarding the other quantifier rules.

答:
Note: I've accepted Mauro ALLEGRANZA's answer, as it was the one that solved the problem for me. However, it didn't really get into the rules. So, to keep a record (and for anyone that also has this question but doesn't want to get into the book), I've come back to complement his answer with an explanation of the ruleset discussed in the book, so that you can use to keep your arguments sound when using any Specification and Generalization.

“I apologize for such a long letter - I didn't have time to write a short one.” - Mark Twain

Before I answer, it's important to note that, as pointed by Mauro, there's no single answer for this question. There are different systems capable of solving the fallacies that generalizations and specifications can bring, and they should not be mixed. If you choose to use this ruleset, or any other, keep in mind that they are meant to be used individually, as mixing them might result in a incomplete (too restrictive) system, or an unsound (illogical) system. So, do not mix rulesets.

For those looking for the original source, the ruleset given here is taken from the book Introduction to Logic (1957), by Patrick Suppes.

Note: You may notice that the naming scheme used here differs from the book ($\alpha$ to $x_\alpha$, flagged variables to distinct variables, ambiguous variables to restricted variables). The reason is that I feel this naming scheme makes the ideas presented more intuitive. However, it's just a matter of presentation. The ideas and rules behind them are the same.

Motivation

Here we show the setbacks, and the natural solutions to them. For now, don't worry about memorizing the rules, as the complete list will be given in the end. This part is only meant build some intuition on why these rules are necessary.

When building an argument using quantifiers, there are 3 main things that we have to pay attention to avoid fallacies:

Mixing different variable classes

Mixing quantifiers

Variables getting caught by different quantifiers

Mixing different variable classes

There are 3 types of free variables:

Those that are free in our premises (as in the premise $P(a)$)

Those that are freed from an exisitential quantifier (as in the deduction $\exists x [P(x)] \vdash P(a)$)

Those that are freed from an universal quantifier (as in the deduction $\forall x [P(x)] \vdash P(a)$)

Treating these classes the same way will quickly lead to fallacies, as shown by the example in the question. Intuitively, the first type represents a distinct variable, a single example from the domain of discourse. The second type represents only objects for which some restricted context applies (i.e. the predicates inside the existential quantifier). The third type represents an object which we have no assumptions about, so any object in the domain of discourse. To avoid confusion, let's separate them:

New concept - Distinct variable: Free variables that represent a specific object from the domain of discourse.

New concept - Restricted variable: Free variables that represent objects restricted by some context.

New concept - Arbitrary variable: Free variables which we have no assumptions about, that may represent any object from the domain of discourse.

Then specify where they appear and some notation so we can differentiate between them:

[1] New $\tt{P}$ rule: Any variable present in an undischarged premise, is a distinct variable. They may be marked on the side of the line in which they are introduced.

[2] New ${\exists}\tt{E}$ rule: Every variable created by ${\exists}\tt{E}$ must be a new/not yet used restricted variable. They may be marked as such with a subscript lowercase greek letter (e.g. $x_\alpha$, $x_\beta$, $y_\gamma$).

[3] New ${\forall}\tt{E}$ rule: Any variable created by ${\forall}\tt{E}$ is an arbitrary variable.

So, in this example:

$$
%PREAMBLE
\newcommand{\nwcm}{\newcommand}
\nwcm{\fitch}[1]{\begin{array}{rlr}#1\end{array}}
\nwcm{\fcol}[1]{\begin{array}{r}#1\end{array}} %FirstColumn
\nwcm{\scol}[1]{\begin{array}{l}#1\end{array}} %SecondColumn
\nwcm{\tcol}[1]{\begin{array}{l}#1\end{array}} %ThirdColumn
\nwcm{\subcol}[1]{\begin{array}{|l}#1\end{array}} %SubProofColumn
\nwcm{\startsub}{\\[-0.29em]} %adjusts line spacing slightly
\nwcm{\endsub}{\startsub} %adjusts line spacing slightly
\nwcm{\fl}{\\[0.044em]} %adjusts line spacing slightly
\nwcm\liff{\leftrightarrow}
\nwcm\lif{\rightarrow}
\nwcm\foll{\forall}
\nwcm\exi{\exists}
\nwcm\tt{\text}
\nwcm\exE{{\exi}\tt{E}}
\nwcm\exI{{\exi}\tt{I}}
\nwcm\follI{{\foll}\tt{I}}
\nwcm\follE{{\foll}\tt{E}}
\fitch{
 \fcol{1:\fl 2:\fl 3:\fl 4:\fl 5:\fl
 }
 & \scol {
  P(a) \\
  \exi x[P(a) \lif Q(x)] \\
  P(a) \lif Q(x_{\alpha}) \\
  Q(x_{\alpha}) \\
  \exi x [Q(x)] \\
 }
 & \tcol{
  \tt{P}[a] \fl
  \tt{P}[a] \fl
  2\ \exE \fl
  1,3\ {\lif}\tt{E} \fl
  3\ \exI \fl
 }
}$$

$a$ is a distinct variable, and is marked as such on the right in line $1$ as "$P[a]$", and $x_{\alpha}$ is a restricted variable, and is marked as such with the $_{\alpha}$ subscript.

Now we may develop some rules to make sure that these definitions are being used in a logical manner. It should be intuitively clear that you may apply $\exI$ with any variable class you wish, but the fallacious example in the question shows that this is not the case with $\follI$, so:

[4]. New $\follI$ rule: You may only generalize from arbitrary variables.

Here's an important note on rule [1]. Arbitrary variables represent an object that we have no assumptions about, so it makes sense that when we introduce a variable in a premise, it's not abitrary, since we've made assumptions about it. However, this also means that if we discharge all assumptions about it, it becomes arbitrary. This is why rule [1] specifies undischarged premises.

Consider this argument: "All pigs are animals. Suppose that a head belongs to a pig. Then the head belongs to an animal. Therefore, all heads of pigs are heads of animals.". Notice that in this argument, the distinct "a head" became the universal "all heads". This happened because the proposition "Suppose that a head [...]" is discharged by the end of the argument. This gets more clear if we formalize the argument:

$$
\fitch{
 \fcol{1:\fl 2:\fl 3:\fl 4:\fl 5:\fl 6:\fl 7:\fl 8:\fl 9:\fl}
 & \scol{
  \foll x[P(x) \lif A(x)]
  \startsub \subcol{
   \exi x[P(x) \land H(y,x)] \\
   \hline
   P(x_\alpha) \land H(y, x_\alpha) \\
   P(x_\alpha) \lif A(x_\alpha) \\
   A(x_\alpha) \\
   A(x_\alpha) \land H(y, x_\alpha) \\
   \exi x[A(x) \land H(y, x)] \\
  } \endsub
  \exi x[P(x) \land H(y,x)] \lif \exi x[A(x) \land H(y, x)] \\
  \foll y [\exi x[P(x) \land H(y,x)] \lif \exi x[A(x) \land H(y, x)]]
 }
 & \tcol{
  \tt{P} \fl
  \tt{P}[y] \fl
  2\ \exE[x/x_\alpha] \fl
  1\ \follE \fl
  3,4\ {\lif}\tt{E} \fl
  3,5\ {\land}\tt{I} \fl
  6\ \exI[x_\alpha/x] \fl
  2,7\ {\lif}\tt{I} \fl
  8\ \follI[y]
 }
}
$$

Line $2$ introduced $y$ in a premise, but that premise is discharged on line $8$, so from that point on, $y$ is arbitrary, and we are free to apply ${\foll}{I}$ on line $9$. So remember, a variable is only distinct if it's in an undischarged premise.

It should also make intuitive sense that we may subsitute an arbitrary variable for a variable of any other class, since it is arbitrary. Here are examples of this happening under $\follE$ and $\exI$, respectively:

$$\begin{array}{rll|rll}
1: & \foll n[n+0=n] & \tt{P}[0]& 1: & \exi x \foll n[n+x=n] & \tt{P} \\
2: & 0+0=0 & 1\ \follE & 2: & \foll n[n+x_{\alpha}=n] & 1\ \exE \\
3: & \exi n[n+n=n] & 2\ \exI & 3: & n+x_{\alpha}=n & 2\ \follE\\
&&& 4: & \exi n[n+n=n] & 3\ \exI[x_{\alpha}/n]\\
\end{array} $$

In the first example, the arbitrary $n$ is substituted for the distinct $0$ in line $2$. In the second one, the arbitrary $n$ is equated with the restricted $x_{\alpha}$ in line $4$. Since they are arbitrary, they may represent any individual or class of objects, no foul play here.

However if a non-arbitrary variable gets equated with a different non-arbitrary variable, that may cause a problem:

$$\begin{array}{rll|rll}
1: & \exi a \exi x[a < x] & \tt{P} & 1: & \exi x[a < x] & P[a] \\
2: & \exi x[a_{\alpha} < x] & 1\ \exE & 2: & a < x_{\alpha} & 1\ \exE \\
3: & a_{\alpha} < x_{\alpha} & 2\ \exE & 3: & \exi a[a < a] & 2\ \exI[x_{\alpha}/a] \tt{(fallacy)} \\
4: & \exi x_{\alpha}[x_{\alpha} < x_{\alpha}] & \exI[a_{\alpha}/x_{\alpha}] \tt{(fallacy)}\\
\end{array} $$

The "$\exi x_{\alpha}$" on the left example is especially silly. The point of restricted variables is to use them as free variables, outside of the existential quantifier, so there is no point using $\exI$ to them. $\exE$ should create restricted variables, and $\exI$ should destroy them. As for the example on the right, we need to make sure that the variable being equated to is arbitrary. So we may state those as:

[5] New $\exI$ rule: Do not generalize to restricted variables.

[6] New $\exI$ rule: You may only generalize to a different variable already present in the formula if it is arbitrary.

So in our left example, line $4$ generalizes to $x_{\alpha}$, which is restricted, breaking rule [5]. In the right one $a$ is distinct, not arbitrary, so step $3$ breaks rule [6].

Two things to note on rule [6]. First, the word "different". As we said before, the problem happens when "a non-arbitrary variable gets equated with a different non-arbitrary variable". If the variable at the end uses the exact same symbol however, it's not getting equated with anybody else, and no problem emerges. So going from $P(x)$ to $\exi x[P(x)]$ is always valid, as they use the same symbol. The second note is on "already present in the formula". If the end variable is not present in the formula, it'll not be equated with any other free variable, so you're safe to generalize to it. So going from $P(x)$ to $\exi a[P(a)]$ is always valid, because $a$ was not present in the formula, even if $a$ is distinct somewhere else.

Another thing worth pointing out is the "new/not yet used" part of rule [2]. As rule [5] resolves the problem of different non-arbitrary variables getting equated for $\exI$, this part of rule [2] does the same for $\exE$. Take this argument:

$$ \begin{array}{rll}
1: & \exi x \exi y[x < y] & \tt{P} \\
2: & \exi y[x_\alpha < y] & 1\ \exE[x/x_\alpha] \\
3: & x_\alpha < x_\alpha & 2\ \exE[y/x_\alpha]\ \tt{(fallacy)} \\
4: & \exi x[x < x] & 3\ \exI \\
\end{array} $$

Here, two non-arbitrary variables under different quantifiers ($x$ and $y$) got equated in line $3$ because a restricted variable was reused, which resulted in a fallacy. So don't forget that part of rule [2], always use a new/not yet used restricted variable on each $\exE$.

With these in place, we won't mix variable classes.

Mixing quantifiers

In this case the first problem is changing the order of quantifiers, which is easy to exemplify. Take the assertion "there's no greatest number", or $\foll x \exi y [x < y]$, if we invert its quantifiers we produce the complete opposite phrase $\exi y \foll x[x < y]$. We may derive this contradiction like so:

$$ \begin{array}{rll}
1: & \foll x \exi y [x < y] & \tt{P} \\
2: & \exi y [x < y] & 1\ \follE \\
3: & x < y_{\alpha} & 2\ \exE \\
4: & \foll x[x < y_{\alpha}] & 2\ \follI \tt{(fallacy)} \\
5: & \exi y \foll x[x < y] & 2\ \exI \\
\end{array} $$

The order of the quantifiers within the same formula should be maintained.

The second one is more subtle:

$$ \begin{array}{rll}
1. & \foll x \exi y [x < y] & \tt{P} \\
2. & \exi y [x < y] & 1\ \follE \\
3. & x < y_{\alpha} & 2\ \exE \\
4. & \exi x[x < x] & 3\ \exI \tt{(fallacy)} \\
\end{array} $$

$x$ is arbitrary, so it would seem that equating $y_{\alpha}$ to it under $\exI$ is fine, but it results in a fallacy. So what is going on here?

When restricted variables were presented, it was mentioned that it "represents only objects for which some restricted context applies (i.e. the predicates inside the existential quantifier)", but what wasn't said on that parenthesis is that not only the predicates are part of the context, but also the free variables within it. In both cases we are failing to account for this, so luckily, we can kill two birds with one stone here.

In the examples above, the restricted variable $y$ depends specifically on being greater than $x$, so we cannot subsitute for it. We may say that the restricted variable depends on the other free variables present. So, let's describe that dependence:

[2] Improved $\exE$ rule: Every variable created by $\exE$ must be a new/not yet used restricted variable. They may be marked as such with a subscript lowercase greek letter (e.g. $x_\alpha$, $x_\beta$, $y_\gamma$). In case there are non-restricted variables free in the formula, they may be added to the subscript (e.g. $x_{\alpha y}$, $x_{\beta zy}$, $y_{\gamma x}$).

[7] New $\exI$ rule: Do not generalize to a variable that is a subscript in the formula.

[8] New $\follI$ rule: Do not generalize to a variable that is a subscript in the formula.

Two points to note. The first one is that rule [2] mentions only non-restricted variables. This is because the other rules we have in place are already enough to stop these problems from occurring for restricted ones (even without the new rules). So, we only need to subscript non-restricted variables. The second one is that being in a subscript counts as "present in the formula". So, the formula $\exi x[P(x,y_{\alpha z})]$ will not become $P(x_{\alpha},y_{\alpha z})$, but $P(x_{\alpha z},y_{\alpha z})$, as $z$ was present in a subscript.

With these rules in place, no quantifiers will be mixed.

Variables getting caught by different quantifiers

When applying some specification, such as $\exE$ or $\follE$, the intention is to free the varable. A specification from a statement like $\foll x \foll y[P(x,y)]$ to $\foll y[P(y,y)]$ is problematic, as the variable was not freed, since it was caught by the "$\foll y$" quantifier.

In the same vein, when applying a generalization, such as $\exI$ or $\follI$, the intention is for the variable to be bounded by the quantifier you just created, and not by any other. That makes a generalization from a statement like $\foll y[P(x,y)]$ to $\exi y \foll y[P(y,y)]$ also problematic, as the variable was caught by the "$\foll y$" quantifier.

This type of deducition can lead to fallacies when applied with any generalization or specification. Here are examples for all of them:

$$\begin{array}{rll|rll}
1: & \foll y \exi x[y < x] & \tt{P} & 1: & \exi x \foll y[x+y=y] & \tt{P} \\
2: & \exi x[x < x] & 1\ \follE \tt{(fallacy)} & 2: & \foll y[y+y=y] & 1\ \exE \tt{(fallacy)} \\
\hline
1: & \foll y \exi x[y < x] & \tt{P} & 1: & \exi x \foll y[x+y=y] & \tt{P} \\
2: & \exi x[y < x] & 1\ \follE & 2: & \foll y[x_{\alpha}+y=y] & 1\ \exE \\
3: & \foll x \exi x[x < x] & 2\ \follI \tt{(fallacy)} & 3: & \exi y \foll y[y+y=y] & 2\ \exI \tt{(fallacy)} \\
\end{array}$$

All of these fallacious arguments stem from the same problem, the variable being freed or bounded getting caught by another quantifier. So even more luckily in this case, we can kill four birds with one stone:

[9] New $\follE$ rule: The variable may not caught by another quantifier.

[10] New $\exE$ rule: The variable may not caught by another quantifier.

[11] New $\follI$ rule: The variable may not caught by another quantifier.

[12] New $\exI$ rule: The variable may not caught by another quantifier.

This might look like a lot, but it's actually just one rule to remember, as it applies to any case. So just remember "your variable may not caught by another quantifier" and you're safe from this one.

Note: In the book, this rule is only given for $\exI$ and $\follE$. The $\exE$ and $\follI$ versions are not strictly necessary for soundness, as other rules already stop these cases (for example, the top right argument already breaks [2]). However, it's way easier to remember it as one single rule for all of them.

Extra rule on restricted variables

It's important to note that there should be no restricted variables present in your conclusion. They are a means to an end, not the end itself. If your conclusion is $P(x_\alpha) \lif Q(x_\alpha)$, what you actually meant was $\exi x[P(x) \lif Q(x)]$. So:

New concept - U-Closure: Any formula that doesn't contain restricted variables has unrestricted closure, or U-Closure.

[13] New rule: All formulas on conclusions should have U-Closure.

[13] might seem like an optional rule, but not using it can lead to a fallacy when you start using derived formulas (i.e. shortcut steps) on your arguments, as two restricted variables from different proofs which happened to use the same symbol might be equated, which would lead to the problem of "mixing non-arbitrary variables". So it is indeed a rule, not a rule of thumb.

It is worth pointing out that "inline conclusions", such as ones from a reductio ad absurdum or a conditional proof do not count as conclusions. This rule is meant only for the actual conclusion of the formal proof.

Summarizing

Now that you know how each rule fits into the construction of a sound deduction system, I can present to you the full list of definitions and rules.

Note that, even though the list is long and verbose, a lot of the rules are repeated, and for some, breaking them looks so wrong that you'll naturally follow them (you may already be actually). Probably the hardest are the ones that manage restricted variables and its subscripts (such as when you have $x_\alpha$, $y_{\alpha x}$, or $z_{\beta b}$). Having that said, here's the list:

Definitions

Distinct Variables: Free variables that represent a distinct object from the domain of discourse.

Restricted Variables: Free variables that represent objects restricted by some context.

Arbitrary variables: Free variables which we have no assumptions about, that may represent any object from the domain of discourse.

U-Closure: If a formula has no restricted variables then it has Unrestricted Closure, or U-Closure.

Rules

Premise: Any free variable present in an undischarged premise, is a distinct variable. They may be marked on the side of the line in which they are introduced for clarity.

Universal Elimination: From $\foll x [P(x)]$ you may derive $P(a)$ if:

$a$ will not be caught by any different quantifier in the result formula.

Existential Elimination: From $\exi x [P(x)]$ you may derive $P(a)$ if:

$a$ will not be caught by any different quantifier in the result formula.

$a$ must be a new/not yet used restricted variable. It may be marked as such with a subscript lowercase greek letter (e.g. $x_\alpha$, $x_\beta$, $y_\gamma$). In case there are non-restricted variables free in the formula, they may be added to the subscript (e.g. $x_{\alpha y}$, $x_{\beta zy}$, $y_{\gamma x}$)

Universal Introduction: From $P(a)$ you may derive $\foll x [P(x)]$ if:

$x$ will not be caught by any different quantifier in the result formula.

$a$ is not present as a subscript in the formula.

$a$ is arbitrary.

Existential Introduction: From $P(a)$ you may derive $\exi x [P(x)]$ if:

$x$ will not be caught by any different quantifier in the result formula.

$a$ is not present as a subscript in the formula.

when $x$ is already present in the formula as a different variable, this variable is arbitrary.

$x$ is not restricted.

General:

All conclusions must have U-Closure.

Tips

Starting the argument

At the start of the argument, you'll usually try to eliminate all the quantifiers first, make your deductions, then reestablish the necessary ones at the end to get U-Closure. Like on the following syllogism:

"All pigs are animals. There are some pigs. Therefore, there are some animals":
$$ \begin{array}{rll}
1: & \foll x [P(x) \lif A(x)] & \tt{P} \\
2: & \exi x[P(x)] & \tt{P} \\
3: & P(x_\alpha) & 2\ \exE \\
4: & P(x_\alpha) \lif A(x_\alpha) & 1\ \follE \\
5: & A(x_\alpha) & 3,4\ {\lif}\tt{E} \\
6: & \exi x[A(x)] & 5\ \exI \\
\end{array} $$

Here we eliminate the quantifiers on lines $3$ and $4$, make our deduction on line $5$, and reestablish the necessary quantifiers on line $6$ to get U-Closure.

Now that you know that structure, here's the tip: At the beginning, eliminate the existentials first, then the universals. Here's the reason: Differently from $\exE$, there's no restriction on $\follE$ saying that we need a new variable, or even if it has to be restricted or not, so we can freely $\follE$ $x$ to $x_\alpha$ on line $4$. In fact, you can $\follE$ to almost any variable. However, let's see at what happens when we try to eliminate the universal quantifier first:
$$ \begin{array}{rll}
1: & \foll x [P(x) \lif A(x)] & \tt{P} \\
2: & \exi x[P(x)] & \tt{P} \\
3: & P(x) \lif A(x) & 1\ \follE \\
? \\
\end{array} $$

Now, we can't do much. We could try to use $\exE$ with line $2$, but that'd give us $P(x_\alpha)$, with a new variable. As $x_\alpha$ is different than $x$, it can not be used with $P(x) \lif A(x)$ to finish the argument. So as a rule of thumb, at the start, $\exE$, only then $\follE$.

Finishing the argument

The tip I just gave has a very important implication: a statement like $\exi x \foll y[P(x,y)]$ is much more useful than $\foll x \exi y[P(x,y)]$. In the former you can $\exE$ first, and then $\follE$, (possibly) making your deductions much easier, while the latter forces you to $\follE$ first. So if you have a statement like $P(x,a_\alpha)$ in your conclusion, assuming that $x$ is arbitrary, you want to end with $\exi a \foll x P(x,a)$ instead of $\foll x \exi a P(x,a)$. So your instinct should be to, at the end, $\follI$, only then $\exI$.

That is not always possible however, since $\follI$ is more restrictive than $\exI$. As an example, let's take $(P(x, a_{\alpha x}) \land Q(y,b_{\alpha xy}))$. Our dream would be to end with $\exi a \exi b \foll x \foll y [(P(x, a) \land Q(y,b))]$, with the existentials first. We're not so lucky on this one though. Notice that the first generalization ($\foll y$) is invalid, since $y$ appears as a subscript in $b_{\alpha xy}$. So, we first have to apply $\exI$ on $b_{\alpha xy}$ to get $\exi b[P(x, a_{\alpha x}) \land Q(y,b)]$ , then, with no $y$ in any subscript, we can $\follI$ it, resulting in $\foll y \exi b [(P(x, a_{\alpha x}) \land Q(y,b))]$. Again, it'd be great to $\follI$ on $x$, but unfortunately, it appears as a subscript on $a_{\alpha x}$, so, we have to $\exI$ it first, getting $\exi a \foll y \exi b [(P(x, a) \land Q(y,b))]$, only then, without $x$ appearing in any subscript, we can $\follI$, resulting in $\foll x \exi a\foll y \exi b [(P(x, a) \land Q(y,b))]$. Not the statement we dreamed about, but the best version we could hope for.

Now, that whole process might have seem a bit convoluted, but in reality there's a nice pattern to it.

To arrive a better U-Closure, use the following steps:

$\follI$ all arbitrary variables that do not appear as a subscript in the formula. Skip this step if there are none.

$\exI$ the restricted variable with the largest amount of subscripts.

Repeat steps 1 and 2 until you arrive at a formula with U-Closure.

This gives you the optimal U-Closed formula in your conclusion.

As an example, here's the optimal U-Closure for the (long) phrase $(P(x, a_{\alpha xy}) \land Q(x,y,b_{\alpha x}) \lif P(z,c_{\alpha yz})) \lor P(z, d_{\alpha xyz})$:

$$
\fitch{
 \fcol{}
 & \scol{
  \exi d [(P(x, a_{\alpha xy}) \land Q(x,y,b_{\alpha x}) \lif P(z,c_{\alpha yz})) \lor P(z, d)] \\
  \exi c \exi d [(P(x, a_{\alpha xy}) \land Q(x,y,b_{\alpha x}) \lif P(z,c)) \lor P(z, d)] \\
  \foll z \exi c \exi d [(P(x, a_{\alpha xy}) \land Q(x,y,b_{\alpha x}) \lif P(z,c)) \lor P(z, d)] \\
  \exi a \foll z \exi c \exi d [(P(x, a) \land Q(x,y,b_{\alpha x}) \lif P(z,c)) \lor P(z, d)] \\
  \foll y \exi a \foll z \exi c \exi d [(P(x, a) \land Q(x,y,b_{\alpha x}) \lif P(z,c)) \lor P(z, d)] \\
  \exi b \foll y \exi a \foll z \exi c \exi d [(P(x, a) \land Q(x,y,b) \lif P(z,c)) \lor P(z, d)] \\
  \foll x \exi b \foll y \exi a \foll z \exi c \exi d [(P(x, a) \land Q(x,y,b) \lif P(z,c)) \lor P(z, d)]
 }
 & \tcol{
  \exI[d_{\alpha xyz}/d] \fl
  \exI[c_{\alpha yz}/c] \fl
  \follI[z] \fl
  \exI[a_{\alpha xy}/a] \fl
  \follI[y] \fl
  \exI[b_{\alpha x}/b] \fl
  \follI[x] \fl
 }
}
$$

Examples

It might be useful to see these in action in some examples, so let's prove some arithmetic facts using the following axioms:

$\tt{Axiom }[a]$: $\foll x \foll y \foll z [x+(y+z)=(x+y)+z]$

$\tt{Axiom }[b]$: $\foll x[x+(-x)=0]$

$\tt{Axiom }[c]$: $\foll x[x+0=x]$

Notice that, since $0$ is free in these axioms, and axioms are never discharged, the variable $0$ is distinct in all of the theorems.

$\tt{Theorem [1]: }\foll x \foll y \foll z [x=y \liff x+z=y+z]$.

$\tt{Proof:}$

$$\fitch{
 \fcol{1:\fl 2:\fl 3:\fl 4:\fl 5:\fl 6:\fl 7:\fl 8:\fl 9:\fl 10:\fl 11:\fl 12:\fl 13:\fl 14:\fl 15:\fl 16:\fl 17:\fl 18:\fl 19:\fl}
 & \scol{
  \subcol{
   x=y \\
   \hline
   x+z = x+z \\
   x+z = y+z
  } \endsub
  x=y \lif x+z=y+z
  \startsub \subcol{
   x+z = y+z \\
   \hline
   (x+z)+(-z)=(x+z)+(-z) \\
   (x+z)+(-z)=(y+z)+(-z) \\
   (x+z)+(-z) = x+(z+(-z)) \\
   (y+z)+(-z) = y+(z+(-z)) \\
   x+(z+(-z))=(y+z)+(-z) \\
   x+(z+(-z))=y+(z+(-z)) \\
   z+(-z) = 0 \\
   x+0=y+0 \\
   x+0=x \\
   y+0=y \\
   x=y
  } \endsub
  x+z=y+z \lif x=y \\
  x=y \liff x+z=y+z \\
  \foll x \foll y \foll z [x=y \liff x+z=y+z]
 }
 & \tcol{
  \tt{P}[x,y] \fl
  {=}\tt{R} \fl
  1,2\ {=}\tt{S} \fl
  1,3\ {\lif}\tt{I} \fl
  \tt{P}[x,y,z] \fl
  {=}\tt{R} \fl
  5,6\ {=}\tt{S} \fl
  [a]\ \follE[x/x,z/(-z),y/z] \fl
  [a]\ \follE[z/(-z),y/z,x/y] \fl
  7,8\ {=}\tt{S} \fl
  9,10\ {=}\tt{S} \fl
  [b]\ \follE[x/z] \fl
  11,12\ {=}\tt{S} \fl
  [c]\ \follE \fl
  [c]\ \follE[x/y] \fl
  13,14,15\ {=}\tt{S} \fl
  5,16\ {\lif}\tt{I} \fl
  4,17\ {\liff}\tt{I} \fl
  18\ \follI \fl
 }
}
$$

Pedantic note: Notice the order in which we $\follE$ line $9$. If we tried specifying $x/y$ first, $y$ would get caught by the quantifier inside at the axiom $[a]$. Same for $z$ if we tried specifying $y/z$ first. So, formally speaking, that order matters.

$\tt{Theorem [2]: }\foll x [x+0=0+x]$.

$\tt{Proof:}$

$$
\fitch{
 \fcol{1:\fl 2:\fl 3:\fl 4:\fl 5:\fl 6:\fl 7:\fl 8:\fl 9:\fl 10:\fl 11:\fl 12:}
 & \scol{
  \subcol{
  x+0 \neq 0+x \\
  \hline
  x+0 = x \\
  x \neq 0+x \\
  x = 0+x \liff x+(-x) = (0+x)+(-x) \\
  x+(-x) \neq (0+x)+(-x) \\
  (0+x)+(-x) = 0+(x+(-x)) \\
  x+(-x) \neq 0+(x+(-x)) \\
  x+(-x) = 0 \\
  0 \neq 0+0 \\
  0 = 0+0
 } \endsub
 x+0 = 0+x \\
 \foll x [x+0 = 0+x] \\
 }
 & \tcol{
  P[x] \fl
  [c]\ \follE \fl
  1,2\ {=}\tt{S} \fl
  [1]\ \follE[x/x,y/(0+x),z/(-x)] \fl
  3,4\ \tt{m.t.} \fl
  [a]\ \follE[x/0,y/x,z/(-x)] \fl
  5,6\ {=}\tt{S} \fl
  [b]\ \follE \fl
  7,8\ {=}\tt{S} \fl
  [c]\ \follE[x/0] \fl
  1,9,10\ \tt{r.a.} \fl
  11\ \follI
 }
}
$$

And to wrap it up, an argument using Existential Quantifiers. Pay special attention on how the previous tip of "at the start $\exE$, only then $\follE$" is used in here (it is used twice, actually! In lines 4-6 and in lines 9-10):

None of Ockham's followers like any realist. All of Ockham's followers likes at least one of Hobbes' followers. Moreover, Ockham does have followers. Therefore, some of Hobbes' followers are not realists.

$$
\fitch{
 \fcol{1:\fl 2:\fl 3:\fl 4:\fl 5:\fl 6:\fl 7:\fl 8:\fl 9:\fl 10:\fl 11:\fl 12:\fl 13:\fl 14:\fl 15:\fl}
 & \scol{
  \foll x [O(x) \lif \foll y [R(y) \lif \lnot L(x,y)]] \\
  \foll x [O(x) \lif \exi y [H(y) \land L(x,y)]] \\
  \exi x[O(x)] \\
  O(x_\alpha) \\
  O(x_\alpha) \lif \exi y [H(y) \land L(x_\alpha,y)] \\
  O(x_\alpha) \lif \foll y [R(y) \lif \lnot L(x_\alpha,y)] \\
  \exi y [H(y) \land L(x_\alpha,y)] \\
  \foll y [R(y) \lif \lnot L(x_\alpha,y)] \\
  H(y_\alpha) \land L(x_\alpha,y_\alpha) \\
  R(y_\alpha) \lif \lnot L(x_\alpha,y_\alpha) \\
        L(x_\alpha,y_\alpha) \\
  \lnot R(y_\alpha) \\
  H(y_\alpha) \\
  H(y_\alpha) \land \lnot R(y_\alpha) \\
  \exi y[H(y) \land \lnot R(y)] \\
 }
 & \tcol{
  P \fl
  P \fl
  P \fl
  3\ \exE[x/x_\alpha] \fl
  2\ \follE[x/x_\alpha] \fl
  1\ \follE[x/x_\alpha] \fl
  4,5\ {\lif}\tt{E} \fl
  4,6\ {\lif}\tt{E} \fl
  7\ \exE[y/y_\alpha] \fl
  8\ \follE[y/y_\alpha] \fl
  9\ {\land}\tt{E} \fl
  10,11\ \tt{m.t.} \fl
  10\ {\land}\tt{E} \fl
  12,13\ {\land}\tt{I} \fl
  14\ \exI[y_\alpha/y]
 }
}
$$


问:
Prove by induction that $\frac{1}{2n}\leq\frac{1\text{·}3\cdot5\text{·}\ldots\text{·}(2n-1)}{2+4+6+\ldots+2n}$
What would be the right way to solve this by induction proof?

$$\frac{1}{2n}\leq\frac{1\text{·}3\cdot5\text{·}\ldots\text{·}(2n-1)}{2+4+6+\ldots+2n}$$

This is what I've done (reference https://www.slader.com/discussion/question/prove-that-12n-1-3-5-2n-12-4-2n-whenever-n-is-a-positive-integer/#):

Show that $S\left(n+1\right)$ by induction proof. This is
$$\frac{1}{2(n+1)}\leq\frac{1\text{·}3\text{·}5\text{·}\ldots\text{·}(2n+1)}{2+4+6+\ldots+2(n+2)}$$

Multiplying both sides of the equation $\frac{2n\text{·}(2(n+1)-1)}{2n\text{·}(2(n+1)-1)}=\frac{2n\text{·}(2n+1)}{2n\text{·}(2n+1)}$

$$\frac{1}{2n}\leq\frac{1\text{·}3\text{·}5\text{·}\ldots\text{·}(2n-1)}{2+4+6+\ldots+2n}\times\frac{2n\text{·}(2(n+1)-1}{2n\text{·}(2(n+1)-1}$$

$$\frac{1}{2n}\times\frac{2n\text{·}(2n+1)}{2n\text{·}(2n+1)}$$
Rewriting we have the following
\begin{array}{c}
\frac{2n+1}{2n(2n+1)}\\
\frac{1}{2n+1}+\frac{1}{2n(2n+1)}
\end{array}

$$\frac{1}{2n}\leq\frac{1}{2n+1}+\frac{1}{2n(2n+1)}$$

答:
$$\frac{1\cdot3\cdot5\cdot\ldots\cdot(2n-1)}{2+4+6+\ldots+2n}\ge \frac{1}{2n}\tag{1} $$
can be simplified as
$$\frac{1\cdot3\cdot5\cdot\ldots\cdot(2n-1)}{n(n+1)}\ge \frac{1}{2n} $$
and then
$$1\cdot3\cdot5\cdot\ldots\cdot(2n-1)\ge\frac{n+1}{2}\tag{2}$$
for $n=1$ we have $1\ge 1$ true.

Now suppose $(2)$ is true and let us prove it for $(n+1)$.

$$[1\cdot3\cdot5\cdot\ldots\cdot(2n-1)](2n+1)\ge \frac{n+1}{2}\cdot(2n+1)\ge\frac{n+1+1}{2}=n+1$$

ContentLicense: CC BY-SA 4.0


问:
How to prove for all $r \in \mathbb{R}$, $\{x \in F \colon f(x) \leq r\}$ is a closed set in $\mathbb{R}$?
Let $F$ be a closed real set and let $f$ be a continuous function $f \colon F \rightarrow \mathbb{R}$.

How can I prove that, for all real number $r$, the set $D = \{x \in F \colon f(x) \leq r\}$ is a closed set?

Thank you.

答:
Assuming that you are essentially supposed to be proving one direction of the equivalence between the metric and topological concepts of "closed", rather than just using the latter:

We wish to show that $\mathbb{R}\setminus D$ is open. That is, given any $x \in \mathbb{R}\setminus D$, we wish to show that there is some $\delta > 0$ such that $(x - \delta, x + \delta) \cap D = \emptyset$.

So, suppose not. Then there is some $x \in \mathbb{R}\setminus D$ such that for any $\delta > 0$, there is some $y_\delta \in (x - \delta, x + \delta) \cap D$. In particular, for every natural $n$, there is some $y_n \in (x - \frac{1}{n}, x + \frac{1}{n})\cap D$.

Now, $|y_n - x| < \frac{1}{n}$ for all $n$, so $(y_n) \to x$.

Since $f$ is continuous, then, $\lim\limits_{n \to \infty}f(y_n) = f\left(\lim\limits_{n \to \infty}y_n\right) = f(x)$.

But also, $y_n \in D$ for all $n$, so $f(y_n) \leq r$ for all $n$. Thus, $\lim\limits_{n\to\infty}f(y_n) \leq \lim\limits_{n\to\infty}r = r$.

Combining these gives $f(x) \leq r$, so $x \in D$, a contradiction.

Thus, we conclude that indeed, $\mathbb{R}\setminus D$ is open, and hence $D$ is closed.


问:
Suppose $B_1 \subseteq A$, $B_2 \subseteq A$, $\sup(B_1)=x_1$ and $\sup(B_2)=x_2$. Prove that if $B_1 \subseteq B_2$, then $x_1 Rx_2$
I'm having trouble with the following proof:

Suppose $\mathcal{R}$ is a partial order on A, $B_1 \subseteq A$, $B_2 \subseteq A$, $\sup(B_1)=x_1$ and $\sup(B_2)=x_2$. Prove that if $B_1 \subseteq B_2$, then $x_1 \mathcal{R}x_2$.

This result seems obvious, but everything I have tried thus far has lead to dead ends. One idea I had is to define $U_1$ as the set of all upper bounds of $B_1$ and and $U_2$ as the set of all upper bounds of $B_2$ and try to show that $U_2 \subseteq U_1$ (this seems to be the case, but I can't find a way to prove this either). Then I could conclude that $x_2 \in U_1$ use the fact that since $\sup(B_1) = x_1$, $\inf(U_1) = x_1$, to conclude $x_1 \mathcal{R} x_2$.

I'm thinking there is a simpler way to go about proving this, but I can't find it. Any help would be appreciated!

答:
Your approach works fine.

If $x\in U_2$, then by definition $b\mathcal{R}x$ for all $b\in B_2$. Let $b\in B_1$ be arbitrary; then $b\in B_2$, so $b\mathcal{R}x$, and since $b\in B_1$ was arbitrary, $x\in U_1$. Thus, $U_2\subseteq U_1$, and you have the rest of the argument.

You can, however, argue a little more directly that if $b\in B_1$, then $b\in B_2$, so $b\mathcal{R}x_2$. Thus, $x_2$ is an upper bound for $B_1$, and hence $x_1\mathcal{R}x_2$. It’s essentially the same argument, of course, but getting more directly to the point.

ContentLicense: CC BY-SA 3.0


问:
Polynomials such that $f_n(x+y, xy) = x^n + y^n$.
What is the pattern in the following polynomials? How can they be easily obtained?
\begin{align*}
   f_1(s, p) &= s \\
   f_2(s, p) &= s^2 - 2p \\
   f_3(s, p) &= s^3 - 3sp \\
   f_4(s, p) &= s^4-4 s^2 p+2 p^2 \\
   f_5(s, p) &= s^5-5 s^3 p+5 s p^2 \\
   f_6(s, p) &= s^6-6 s^4 p+9 s^2 p^2-2 p^3   \\
             &\vdots
\end{align*}
These polynomials express the sums of $n$th powers of two variables $x$ and $y$ in terms of their sum ($s$) and product ($p$).

答:
You can find recursively as:
$$
f_{n+1}(s,p)=s f_n(s,p)-p f_{n-1}(s,p)
$$


问:
Show that $EF$ is a subfield of $L$.
Consider the field extension $L:K$, with finite degree, and consider $E$, $F$ two intermediate field.

Define,
$$EF=\left\{ \sum_{1\leq i\leq n} x_iy_i; n\in \mathbb{N}^*, x_i\in E, y_i\in F, \ \forall i(1\leq i\leq n) \right\}.$$

Show that $EF$ is a subfield of $L$. (It's enough to show that it is a domain of integrity, there's a proposition that takes from there.) I am having trouble to show the properties of the multiplication, there's a easy way to do this?

Check that $EF$ is the sub field of $L$ generated by $E\cup F$.

答:
The key fact on which this exercise is based is that the set $EF$ is contained in $L$, a field, therefore we can nicely operate on its elements. Indeed, an element of the form $\sum_i x_iy_i=x_1y_1+\cdots+x_ny_n$ is well defined since for every $i$, $x_i\in E\subset L$, $y_i\in F\subset L$, and in $L$ we can sum and multiply.

Step 1: $EF$ is an abelian group. The addition is the following: $$(x_1y_1+\cdots+x_ny_n)+(z_1w_1+\cdots+z_mw_m)=x_1y_1+\cdots+x_ny_n+z_1w_1+\cdots+z_mw_m.$$ All this is happening in $L$. Clerly we get an element again in $EF$, and this operation is trivially associative. The neutral element is $0\in L$, it belongs to $EF$ since for example it can be written as $0_E\cdot 0_F$, and the opposite of $\sum_i x_iy_i=x_1y_1+\cdots+x_ny_n$ is $\sum_i -x_iy_i=-x_1y_1-\cdots-x_ny_n\in EF$. Indeed: $$x_1y_1+\cdots+x_ny_n+(-x_1y_1-\cdots-x_ny_n)=x_1y_1-x_1y_1+\cdots+x_ny_n-x_ny_n=0,$$ where again this is happening in $L$, which is commutative as additive group. We conclude that $EF$ has a natural structure of abelian group.

Step 2: EF is a ring. The product is defined using the product of $L$ and the distributive property. To lighten the notation, I make a simple example: $$(x_1y_1+x_2y_2)\cdot(z_1w_1+z_2w_2+z_3w_3)=x_1y_1z_1w_1+x_1y_1z_2w_2+x_1y_1z_3w_3+x_2y_2z_1w_1+x_2y_2z_2w_2+x_2y_2z_3w_3.$$ Again, this is happening in $L$, a commutative ring, so we can commute elements of the form $x_iy_iz_jw_j$, writing $$x_iy_iz_jw_j=x_iz_jy_iw_j$$ and deducing that $EF$ is closed under this product. The identity element is $1\in L$, we can write it as $1_E\cdot 1_F$, and as for the sum, associativity (and also distributivity) follow straightforwardly (try to do it yourself if you are not convinced).

Step 3: now $EF$ is clearly an integral domain, being a subring of a field. Can you conclude (with your proposition) that $EF$ is actually a subfield? (here you surely need that the two extensions are finite and therefore algebraic over $K$, otherwise it is not always true that $EF$ is a field. See for example Is the composite of two subfields just their product?).

Step 4: $EF$ is the field generated by $E\cup F$, that is, it is the smallest subfield of $L$ containing $E\cup F$. Indeed, it is a field, it contains both, so it contains the union, and if $\Omega$ is a field containing $E\cup F$, then it contains all the possibile sums $x_1y_1+\cdots+x_ny_n$, so it has to contain $EF$.

I hope this is clear.

Title: Show that $EF$ is a subfield of $L$.


答:
Let $\varphi, \psi:\mathbb N\to\mathbb N$ given by
\begin{aligned}
\varphi(n) &= \sum_{k=1}^n 2k = n(n+1)\\
\psi(n) &= \prod_{k=1}^n (2k-1)\\
\end{aligned}
and notice that
\begin{aligned}
\varphi(n+1) &= \frac{n+2}n\varphi(n)\\
\psi(n+1) &= (2n+1)\psi(n)\\
\end{aligned}

If you assume that, for a certain $n\in\mathbb N$, the following is true
$$\frac 1{2n}\le \frac{1\times 3\times\ldots\times (2n-1)}{2 + 4 + \ldots + 2n} = \frac{\psi(n)}{\varphi(n)},$$
then you may write
\begin{aligned}
\frac 1{2(n+1)}
& = \frac{2n}{2(n+1)}\frac1{2n}\\
& \le \frac{2n}{2(n+1)}\frac{\psi(n)}{\varphi(n)}\\
& = \frac{2n}{2(n+1)}\frac1{2n+1}\frac{n+2}{n}\frac{\psi(n+1)}{\varphi(n+1)}\\
& = \frac{n+2}{(n+1)(2n+1)}\frac{\psi(n+1)}{\varphi(n+1)}\\
& \le \frac{\psi(n+1)}{\varphi(n+1)},
\end{aligned}

where the last inequality follows from the fact that

$$
\frac{n+2}{(n+1)(2n+1)} = \frac{1}{2n+1}\left(1 + \frac1{n+1}\right) \le \frac 12\left(1 + \frac 12\right) = 1.
$$

Title: Prove by induction that $\frac{1}{2n}\leq\frac{1\text{·}3\cdot5\text{·}\ldots\text{·}(2n-1)}{2+4+6+\ldots+2n}$

Body:
What would be the right way to solve this by induction proof?

$$\frac{1}{2n}\leq\frac{1\text{·}3\cdot5\text{·}\ldots\text{·}(2n-1)}{2+4+6+\ldots+2n}$$

This is what I've done (reference https://www.slader.com/discussion/question/prove-that-12n-1-3-5-2n-12-4-2n-whenever-n-is-a-positive-integer/#):

Show that $S\left(n+1\right)$ by induction proof. This is
$$\frac{1}{2(n+1)}\leq\frac{1\text{·}3\text{·}5\text{·}\ldots\text{·}(2n+1)}{2+4+6+\ldots+2(n+2)}$$

Multiplying both sides of the equation $\frac{2n\text{·}(2(n+1)-1)}{2n\text{·}(2(n+1)-1)}=\frac{2n\text{·}(2n+1)}{2n\text{·}(2n+1)}$

$$\frac{1}{2n}\leq\frac{1\text{·}3\text{·}5\text{·}\ldots\text{·}(2n-1)}{2+4+6+\ldots+2n}\times\frac{2n\text{·}(2(n+1)-1}{2n\text{·}(2(n+1)-1}$$

$$\frac{1}{2n}\times\frac{2n\text{·}(2n+1)}{2n\text{·}(2n+1)}$$
Rewriting we have the following
\begin{array}{c}
\frac{2n+1}{2n(2n+1)}\\
\frac{1}{2n+1}+\frac{1}{2n(2n+1)}
\end{array}

$$\frac{1}{2n}\leq\frac{1}{2n+1}+\frac{1}{2n(2n+1)}$$


问:
Construct a finite field of 128 elements.
By using Galois' Theorem I know I need to find an irreducible polynomial of degree 7 in $\mathbb{Z}_2$. However I'm not sure how to find one efficiently, without showing that it is not the product of a polynomial of degree 5 and another of degree 2, or one of degree 3 and another of degree 4.

答:
I’m hoping that you know how to raise something to a ridiculously high power by means of ridiculously few multiplications.

Well, you’re looking for an irreducible septic polynomial $f(x)$ over $\Bbb F_2$, the field with two elements. There are eighteen of them, not so many when you consider how many polynomials over $\Bbb F_2$ of degree seven there are. Nonetheless, I recommend flailing about and trying random polynomials that may work.

How do you tell that your ring $K_f=\Bbb F_2[x]/\bigl(f(x)\bigr)$ really is a field? As long as your chosen $f$ has no repeated factors, this $K_f$ will be a direct sum of fields. And if $f$ is reducible, there will be at least two of these, all rather smaller than $\Bbb F_{128}$, and certainly no element in any such thing will be of order $127$, a property that all the elements of $\Bbb F_{128}$, except for $0$ and $1$, will have.

Thus, if any element of $K_f$ has order $127$, then $K_f$ is a field. For instance, if I take $f(x)=x^7+x^2+1$, then $x^{127}=x^6+x^4+1$. Bad guess! But try Darsen’s guess, from an earlier answer, now deleted, of $f(x)=x^7+x+1$, really the first guess you ought to examine. Lo and behold!, you get $x^{127}=1$, and just to check, $(1+x^2+x^5)^{127}=1$ as well, as must be.

So there you are, with a nice septic irreducible polynomial over $\Bbb F_2$ .


问:
How to derive the law of total probability for three or more RVs?
I'm confused about the generalization of the law of total probability (or sum rule) for more than two Random Variables. For two RVs, it is defined as
$$
P(X=x) = \sum_{y\in \mathcal{Y}}P(x,y).
$$
However, I'd like to clarify how this generalizes to more than two RVs. What I've tried is a simple analogy, e.g. for three RVs:
$$
P(X=x) = \sum_{y\in \mathcal{Y}}\sum_{z\in \mathcal{Z}}P(x,y,z).
$$
I'm not sure about is whether the analogy is correct and whether some prior must be considered in between the steps of the computation, e.g. is it needed to consider $P(Y)$ if I still need to compute $P(x,y,Z)$? I'm possibly confused with the conditional form of this.

Also it causes confusion for me when I see
$$
P(X_1) = \sum_{i=2}^\ell P(X_1,X_i)
$$
because I'm not sure whether $X_i$ (i=1,\dots,\ell) can be considered different RVs or $X_i$ are instances of some RV $X$.
I'll be grateful if you can give also general advise on this theme. Thank you very much

答:
When dealing with discrete random variables, $X,Y$, whose probability mass function are supported over intervals $\mathcal X,\mathcal Y$, the Law of Total Probability states:

$$\mathsf P(X{=}x)=\sum_{y\in\mathcal Y}\mathsf P(X{=}x,Y{=}y)$$

Or $$P_{\small X}(x)=\sum_{y\in\mathcal Y} P_{\small X,Y}(x,y)$$

Of course this can be expanded to more such random variables.  Say by adding $Z$

$$\mathsf P(X{=}x)=\sum_{y\in\mathcal Y}\sum_{z\in\mathcal Z}\mathsf P(X{=}x,Y{=}y, Z{=}z)$$

Or $$P_{\small X}(x)=\sum_{y\in\mathcal Y}\sum_{z\in\mathcal Z} P_{\small X,Y,Z}(x,y,z)$$

Basically the probability mass of event $\{X=x\}$ equals the sum of the probability mass of disjoint events $\{X=x,Y=y,Z=z\}$ for all supported values for $y, z$; because $\{X=x\}$ equals the union of all these disjoint events.

Also it causes confusion for me when I see: $$P(X_1) = \sum_{i=2}^\ell P(X_1,X_i)$$

Indeed, in such an expression, those do not appear to be random variables at all, but rather events. To be clear, let us use some different letters for them. Specifically when $A$ is an event and ${\{B_i\}}_{i=1}^\ell$ is a sequence of $\ell$ disjoint events that partition over $A$  [that is, $A\subseteq \bigcup_{i=1}^\ell\{ B_i\}$ ], then:$$\mathsf P(A)=\sum_{i=1}^\ell\mathsf P(A\cap B_i)$$


问:
How do ring morphisms work when dealing with polynomial rings?
I've been trying to understand how ring morphisms work when dealing with polynomial rings, but I'm having a little bit of trouble understanding how they work.

Let $R,S$ be rings (they need not be commutative nor have a multiplicative identity) and $f:R\to S$ a ring morphism. We know that this induces a ring morphism $f^*:R[x]\to S[x]$ given by $f^*(a_0+a_1x+\cdots+a_nx^n)=f(a_0)+f(a_1)x+\cdots+f(a_n)x^n$. My problem now is: is every ring morphism $F:R[x]\to S[x]$ of the form $F=g^*$ for some $g:R\to S$?

I don't know whether it is or not the case, but if it is I'm having trouble proving it.

My first approach would be that any polynomial can be thought as a sum and product of constant polynomials and $x^k$ for some $k$ and in that sense, then $F(a_0+\cdots a_nx^n)=F(a_0)+\cdots F(a_n)F(x)^n$, so if I knew that $F$ sends constant polynomials to constant polynomials and polynomials of the form $x^n$ to themselves, then I would have the desired result, but this is something I haven't been able to prove yet.

Only thing I know is that for $c\in R$, $F(c)=b_0+\cdots+b_mx^m$ with $b_i\in S$ for all $i$, but I can't deduce from there that $b_i=c$ if $i=0$ and $b_i=0$ otherwise. Same case with $x^n$ .

If this is not the case, however, and I'm trying to prove something false, then how do these morphisms work? Is there a way to more or less understand their behaviour?

Any help is thanked for :)

答:
The result is not true:

Take $R = S = \mathbb{Z}[y]$. Then $R[x] = S[x] = \mathbb{Z}[x,y]$ has an automorphism given by sending $x$ to $y$ and $y$ to $x$. This cannot be of your desired form, as it sends (for example) the polynomial $x$ to something in $S$, but any map of your desired form must send it to something of the form $sx$, where $s \in S$, which does not lie in $S$.

What your approach gives you is a grading on $R[x]$ (indeed, the very prototypical example of a grading). That is: a collection of subsets $R_i$ with $R = \bigoplus R_i$ as additive groups, such that if $a \in R_i$ and $b \in R_j$, then $ab \in R_{i+j}$: the grading is precisely by $x$-degree, so that $R_i = \{ax^i | a \in R\}$. Then each element of $R[x]$ is a sum of one element from each $R_i$, as you've written.

With that, then, the morphisms that do what you ask for are precisely the graded morphisms (with respect to this grading): that is, the morphisms $\varphi: R[x] \to S[x]$ such that $\varphi(R_i) \subseteq S_i$ for all $i$. Your problems, though, are twofold:

Gradings are very much not unique, and there's nothing that particularly privileges your choice of grading over any other.

It is not true, in general, that all morphisms are graded morphisms with respect to your particular grading. Indeed, if $R$ has a non-trivial grading, then it has non-zero morphisms $R \to R_0$, where $R_0$ is the graded component containing the identity (the simplest example is $E_0$, which is just the projection onto the $R_0$ summand). This cannot be graded. In the case of polynomial rings, things are actually worse for you: in $R[x]$, the above map is precisely evaluation at $0$. There is a similar evaluation morphism $E_s$ for any other $s \in R$, which has the same problem. Indeed, the only ring for which your result does hold is the trivial ring $0$ (just because then $0[x] = 0$, so the only homomorphism $0[x] \to 0[x]$ is the zero homomorphism $0 = 0^*$.


问:
Showing that $\sqrt \pi$ is transcendental
I'm trying to use the fact that $\pi$ is transcendental to show that $\sqrt \pi$ is also transcendental over $\Bbb{Q}$ . I don't know any theorems about algebraic and non-algebraic numbers so I don't have much in my tool box. Here's what I have done so far :

Let $P(x) \in \Bbb{Q}[x]$ and write $P(x)$ in the following way $$P(x)= \underbrace{ \left ( \sum_{\text{$j$ even}} a_j x^j +a_0 \right ) }_{Q(x)}+\underbrace{\sum_{\text{$i$ odd}} a_i x^i }_{G(x)}$$ Then $P(\sqrt \pi )= Q (\sqrt \pi) + G(\sqrt \pi)$ , $ Q (\sqrt \pi) =\displaystyle \sum_{\text{$j$ even}} a_j  \sqrt\pi ^j+a_0  =\sum_{\text{$j$ even}} a_j \pi^{\frac j 2} +a_0$ hence $Q (\sqrt \pi) \not= 0$ since $\pi$ is transcendental, Similarly I showed $G(\sqrt \pi)$ is also non zero by taking $\sqrt \pi$ as a common factor. I'm now stuck on showing that $G(\sqrt \pi) \not= -Q(\sqrt \pi) $ . If can prove that then $P(\sqrt \pi) \not= 0$.  How can it be done?

答: I found another way to solve it, suppose that $\sqrt \pi$ is a root of $P(x)$ which is defined in the question then we have$$  \left ( \sum_{\text{$j$ even}} a_j \pi^{\frac j 2} +a_0 \right ) +\sqrt \pi \sum_{\text{$i$ odd}} a_i \pi^{i-1} = 0 $$ then $Q(\pi)=-\sqrt \pi G(\pi)$ upon squaring both sides we get $Q^2(\pi)= \pi G^2(\pi)$ then $Q^2(\pi)- \pi G^2(\pi)=0$ is a polynomial in $\pi$ equal to zero which is a contradiction since $\pi$ is transcendental. </p>


问:
How do I use a known pattern to get a closed formula for a sequence?
I have a sequence with a very predictable pattern. It goes like this:

$$2,1,4,2,1,1,8,2,1,4,2,1,1,1,16,2,1,4,2,1,1,8,2,1,4,2,1,1,1,1,32,2,1,4,2,1,1,8,2,1,4,2,1,1,1,16,2,1,4,2,1,1,8,2,1,4,2,1,1,1,1,1,64, 2, 1, 4, 2, 1, 1, 8, 2, 1, 4, 2, 1,1 ,1 , 16, 2, 1, 4, 2, 1, 1, 8 \dots$$

Every term is some power of $2$, and $2^n$ will show up for the first time at the $\left(2^n-1\right)^\text{th}$ term in the sequence, and it will be preceded by $n-1$ ones.

I can write more terms, for as far as I wanted to. The problem is, I want to be able to know something like $4000^\text{th}$ term, without having to write the sequence all the way up to $4000$. How do I go from the known pattern to the closed formula for the $n^\text{th}$ term? Or maybe recurrence formula?

I don't know how to go from the pattern to a formula. Thanks for help.

答: Note that the terms preceding $16$, for example, are always the same.  There are $14$ of them.  The pattern starts after any higher power of $2$.  You should be able to justify that this is true for any given power of $2$.  You can approach any given term by successive powers of $2$.  Taking term $4000$ for example, the $2047^{th}$ term is $4096$.  The $4000^{th}$ term will be the same as the $4000-2047=1953^{rd}$  The next power below $1953$ is $2048$, which occurs in the $1023^{rd}$ term.  Term $1953$ is the same as term $1953-1023=930$.  Keep going.  This gives a recursive algorithm.  Given a term number $n$ it will take about $\log_2(n)$ steps


问:
Average of the elements of an infinite series
Let $a$ be a series of natural numbers where
$$
a_k=\begin{cases}
\frac{2(k+1)}{3} & \text{if }(k \mod3)=2\\
1 & \text{otherwise}
\end{cases}
$$
for every $k\in\mathbb{Z}^+$. The question is what is the average of the reciprocal of all these elements. Expressed as a summation it looks like this:
$$\lim_{n\to\infty}\frac{1}{n}\sum_{k=1}^{n}\frac{1}{a_k}
$$
Now if we look at the series, it looks like this $\{1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, 1, 12, 1, 1, 14, 1, 1, 16, 1, \dots\}$. What I tried to do was split the summation into three summations, becuase notice that there are groups of three. First, comes a $1$, then comes that value from the mod and then another $1$. I tried grouping these in the summation like this:
$$\lim_{n\to\infty}\frac{1}{n}\left(\left(2\sum_{k=1}^{n/3}1\right)+\sum_{m=1}^{n/3}\frac{1}{\frac{2(3(m-1)+1)}{3}}\right)=\lim_{n\to\infty}\frac{1}{n}\left(\frac{2n}{3}+\sum_{m=1}^{n/3}\frac{1}{2m}\right)
$$
I tried various methods to solve it from here but I kept getting $2$ as a result, which should be impossible $a$ is a series for natural numbers and the highest value this should return should be $1$ for an infinite series of $1$-s.

Any help is appreciated. If you don't tell me the answer, that's also fine as long as someone tells me what I did wrong and how I should have done it or how I should solve the limit, because at this point I have no idea.

答:
After looking at the thing I wrote, I realized how stupid am I. My problem was not dividing the $2n$ by 3, which lead to me getting $2$ as a result. I'll still post the solution to the sum.

The partial sum of that summation looks like this:
$$\frac{2}{3}+\lim_{n\to\infty}\frac{\gamma+\psi^{(0)}(1+\frac{n}{3})}{n}
$$
The limit evalutes to $0$ thus the answer is $0.\bar{6}$, which does satisfy the condition of it being lower than $1$.


答:
Setting $p=-1$, these are Lucas polynomials:

$$L_n(x) = 2^{-n} \left((x-\sqrt{x^2+4})^n + (x+\sqrt{x^2+4})^n  \right)$$

Your coefficients correspond to OEIS A034807 and may be expressed in terms of Lucas numbers.

Thanks to Steven Stadnicki for him comment below pointing out that the $p$ powers can be inferred, so setting $p=-1$ is WLOG.

For completion:

By induction, we may prove that your sequence satisfies the relation
$$f_{n} = s f_{n-1} - p f_{n-2}$$
with $f_0=2$ and $f_1=s$.

We have seen that the base case $n=2$ works. Suppose the relation $f_{n} (x+y, xy)=x^n+y^n$ holds for integers below $n$. Then,

$$f_{n} (x+y, xy) = (x+y)(x^{n-1}+y^{n-1}) - xy (x^{n-2}+y^{n-2}) = x^n+y^n$$

Your sequence may thus be expressed generally as a Lucas Polynomial Sequence:

$$f_n = 2^{-n} \left[\left(s+\sqrt{s^2-4p}\right)^n + \left(s-\sqrt{s^2-4p}\right)^n \right]$$

Title: Polynomials such that $f_n(x+y, xy) = x^n + y^n$.

Body:
What is the pattern in the following polynomials? How can they be easily obtained?
\begin{align*}
   f_1(s, p) &= s \\
   f_2(s, p) &= s^2 - 2p \\
   f_3(s, p) &= s^3 - 3sp \\
   f_4(s, p) &= s^4-4 s^2 p+2 p^2 \\
   f_5(s, p) &= s^5-5 s^3 p+5 s p^2 \\
   f_6(s, p) &= s^6-6 s^4 p+9 s^2 p^2-2 p^3   \\
             &\vdots
\end{align*}
These polynomials express the sums of $n$th powers of two variables $x$ and $y$ in terms of their sum ($s$) and product ($p$).


问:
Unique parsing means?
After searching this site for the key words "unique parsing" "parsing" and "unique parsing lemma," and finding nothing really applicable to me (or as far as I could tell), I decided to post the question. I'm not a math person, or logic.. so if anybody can even just tell me what on earth is this question even asking us to do... that'd be appreciated. If you have further insight on how to approach solving this, then that'd be great.

Prove the unique parsing lemma for first-order predicate logic (which includes identity
and complex terms). That is, let ∝ be a well-formed formula of first-order predicate logic.
Prove that exactly one of the following holds:

(i) ∝ is atomic.

(ii) ∝  has the form ~β for some well-formed formula β.

(iii) ∝  has the form (β -> γ ) for some well-formed formulae β and γ.

(iii) ∝  has the form (β & γ) for some well-formed formulae β and γ.

(iv) ∝  has the form (β v γ) for some well-formed formulae β and γ.

(v) ∝  has the form ∀vβ for some variable v and some well-formed formula β.

(v) ∝  has the form ∃vβ for some variable v and some well-formed formula β.

答:
This result - more commonly called "unique readability" - basically says that there's only one way to interpret a well-formed formula. To see what could go wrong in principle, suppose we didn't include parentheses in our syntax for first-order logic. Then we'd wind up (for example) with formulas which look like $$a\wedge b\vee c.$$ It's unclear what this means: is it "$(a\wedge b)\vee c$" or "$a\wedge (b\vee c)$"? We could resolve this by adding some PEMDAS-like rules for order of operations, but it winds up being more convenient to just use a syntactical construction which prevents these issues from arising in the first place.

The phrasing of the lemma reflects the idea of evaluating a formula by breaking it into its constituents until we get "all the way down" to atomic formulas; the fact that exactly one case holds for any given formula tells us that there's never any ambiguity as to how to perform this breaking-down process.

Title: Unique parsing means?


问:
Can you have a matrix with no zero rows that has an eigenvalue equal to zero
Can you have a matrix with no zero rows that has an eigenvalue equal to zero?

So for $A \in \mathbb{R}^{n \times n}$ with $0$ as an eigenvalue, is the $\text{rank}(A)$ always smaller than $n$?

答:
Consider the matrix $A \in \mathbb{R}^{n \times n}$ obtained as $uv^T$, where $u,v \in \mathbb{R}^{n \times 1}$ and none of the entries of $u$ and $v$ are zero.

$\color{blue}{\text{This matrix $A = uv^T$ has no zero entries since $A(i,j) = u(i)v(j)$, where both $u(i)$ and $v(j)$ }}$ $\color{blue}{\text{are non-zero for all $i,j \in \{1,2,\ldots,n\}$}}$.

However, $\color{red}{\text{the matrix $A$ has $n-1$ eigenvalues as zero}}$.

One of the many equivalent definitions of rank of a matrix is the number of non-zero eigenvalues of the matrix. Hence, if $r$ eigenvalues of a matrix are non-zero, then the matrix has rank $r$.


问:
$(a^4+b^2) \leq (a^2+b^2)^2$ for all $a, b \in \mathbb{R}_+$?
Let $a, b \in \mathbb{R}_+$.

Question. Is valid that
$$(a^4+b^2) \leq (a^2+b^2)^2?\tag{1}$$

I tried what follows:
$$(a^2+b^2)^2=a^4+2a^2b^2+b^4 \geq a^4+2a^2b^2.$$
For this, can I to conclude that $(1)$ holds?

答:
HINT

You can simply expand the RHS and subtract the LHS:
\begin{align*}
(a^{2} + b^{2})^{2} = a^{4} + 2a^{2}b^{2} + b^{4} \Rightarrow (a^{2} + b^{2})^{2} - a^{4} - b^{2} = 2a^{2}b^{2} + b^{4} - b^{2} = b^{2}(2a^{2} + b^{2} - 1)
\end{align*}

When the last expression is nonnegative?

 Answer: outside the ellipse $2a^{2} + b^{2} = 1$


答:
$a=0, b=\frac 1 2 $ is a counter-example.

If $0$ is not allowed just take $a>0$ but small enough. Eg: $a=\frac 1 {10}$ will do.

Title: $(a^4+b^2) \leq (a^2+b^2)^2$ for all $a, b \in \mathbb{R}_+$?

Body:
Let $a, b \in \mathbb{R}_+$.

Question. Is valid that
$$(a^4+b^2) \leq (a^2+b^2)^2?\tag{1}$$

I tried what follows:
$$(a^2+b^2)^2=a^4+2a^2b^2+b^4 \geq a^4+2a^2b^2.$$
For this, can I to conclude that $(1)$ holds?


Body:
$$\bigg( \left(\frac{1}{2} \right)^2+ \left(\frac{1}{2} \right)^2 \bigg)^2=\left(\frac{1}{2}\right)^2=\frac{1}{4}$$
but
$$\bigg( \left(\frac{1}{2}\right)^4+ \left(\frac{1}{2}\right)\bigg)^2= \left(\frac{1}{2}\right)^4+\frac{1}{4} > \frac{1}{4}= \bigg( \left(\frac{1}{2} \right)^2+ \left(\frac{1}{2}\right)^2 \bigg)^2$$


问:
Solving $(x\cos y - y\sin y)dy - (x\sin y + y\cos y)dx =0$.
$$(x\cos y - y\sin y)dy - (x\sin y + y\cos y)dx =0.$$

I know that this is not an exact differential equation. So I have tried various integrating factors that I know. How can I solve this using an exact differential equation? In fact, can it even be solved by this method? If not then can someone please tell me how it can be done?

答:
$(x\cos y-y\sin y)~dy-(x\sin y+y\cos y)~dx=0$

$(x\sin y+y\cos y)~dx=(x\cos y-y\sin y)~dy$

$(x+y\cot y)\dfrac{dx}{dy}=x\cot y-y$

This belongs to an Abel equation of the second kind.

Let $u=x+y\cot y$ ,

Then $x=u-y\cot y$

$\dfrac{dx}{dy}=\dfrac{du}{dy}+y\csc^2y-\cot y$

$\therefore u\left(\dfrac{du}{dy}+y\csc^2y-\cot y\right)=(u-y\cot y)\cot y-y$

$u\dfrac{du}{dy}+(y\csc^2y-\cot y)u=u\cot y-y\cot^2y-y$

$u\dfrac{du}{dy}=(2\cot y-y\csc^2y)u-y\csc^2y$


Body:
CW answer. It means Country Western.

Note how the column with coefficients of $p^2$  has the integer part, 2, 5, 9, 14, 20, 27, 35, 44,  is quadratic in $n$

parisize = 4000000, primelimit = 500000
? f1 = s
%1 = s
? f2 = s^2 - 2 * p
%2 = s^2 - 2*p
? f3 = s * f2 - p * f1; f1 = f2; f2 = f3
%3 = s^3 - 3*p*s
? f3 = s * f2 - p * f1; f1 = f2; f2 = f3
%4 = s^4 - 4*p*s^2 + 2*p^2
? f3 = s * f2 - p * f1; f1 = f2; f2 = f3
%5 = s^5 - 5*p*s^3 + 5*p^2*s
? f3 = s * f2 - p * f1; f1 = f2; f2 = f3
%6 = s^6 - 6*p*s^4 + 9*p^2*s^2 - 2*p^3
? f3 = s * f2 - p * f1; f1 = f2; f2 = f3
%7 = s^7 - 7*p*s^5 + 14*p^2*s^3 - 7*p^3*s
? f3 = s * f2 - p * f1; f1 = f2; f2 = f3
%8 = s^8 - 8*p*s^6 + 20*p^2*s^4 - 16*p^3*s^2 + 2*p^4
? f3 = s * f2 - p * f1; f1 = f2; f2 = f3
%9 = s^9 - 9*p*s^7 + 27*p^2*s^5 - 30*p^3*s^3 + 9*p^4*s
? f3 = s * f2 - p * f1; f1 = f2; f2 = f3
%10 = s^10 - 10*p*s^8 + 35*p^2*s^6 - 50*p^3*s^4 + 25*p^4*s^2 - 2*p^5
? f3 = s * f2 - p * f1; f1 = f2; f2 = f3
%11 = s^11 - 11*p*s^9 + 44*p^2*s^7 - 77*p^3*s^5 + 55*p^4*s^3 - 11*p^5*s
? f3 = s * f2 - p * f1; f1 = f2; f2 = f3
%12 = s^12 - 12*p*s^10 + 54*p^2*s^8 - 112*p^3*s^6 + 105*p^4*s^4 - 36*p^5*s^2 + 2*p^6
? f3 = s * f2 - p * f1; f1 = f2; f2 = f3
%13 = s^13 - 13*p*s^11 + 65*p^2*s^9 - 156*p^3*s^7 + 182*p^4*s^5 - 91*p^5*s^3 + 13*p^6*s
? f3 = s * f2 - p * f1; f1 = f2; f2 = f3
%14 = s^14 - 14*p*s^12 + 77*p^2*s^10 - 210*p^3*s^8 + 294*p^4*s^6 - 196*p^5*s^4 + 49*p^6*s^2 - 2*p^7
? f3 = s * f2 - p * f1; f1 = f2; f2 = f3
%15 = s^15 - 15*p*s^13 + 90*p^2*s^11 - 275*p^3*s^9 + 450*p^4*s^7 - 378*p^5*s^5 + 140*p^6*s^3 - 15*p^7*s
? f3 = s * f2 - p * f1; f1 = f2; f2 = f3
%16 = s^16 - 16*p*s^14 + 104*p^2*s^12 - 352*p^3*s^10 + 660*p^4*s^8 - 672*p^5*s^6 + 336*p^6*s^4 - 64*p^7*s^2 + 2*p^8
?


问:
Surjectivity of natural morphism between multiplicative modulo groups
Let $n$ be an integer and $d$ be a divisor of $n$. Then there is a natural group homomorphism:
\begin{align}\varphi:(\mathbb{Z}/n\mathbb{Z})^{\times} &\to (\mathbb{Z}/d\mathbb{Z})^{\times}\\ [x] &\mapsto [x] \end{align}
I want to know whether $\varphi$ is surjective. This may be a silly question, but I don't know where to look for the answer. Any help would be appreciated.

答:
By $\,\rm\color{#c00}{co}$prime Dirichlet: $\,(a,d,n)\overset{d\,\mid\, n}=(a,d)=1\,\Rightarrow\, \exists\, x\in\Bbb Z\!:\ (a+d\:\!x,\,n)=1.\ \ \rm\small QED$

Remark $ $ This theorem on $\rm\color{#c00}{co}$primes in arithmetic progressions has a very short high-school level proof using a simple variation (by Stieltjes) on Euclid's proof that there are infinitely many primes.


问:
if $n>0$ and $r>0$ ($n$ and $r$ and positive integers) and $r$ divides $n$ , then $n/r$ divides $nCr$ . Is this statement true?

if $n>0$ and $r>0$ ($n$ and $r$ and positive integers), and $r$ divides $n$, does $n/r$ divides $\binom{n}{r}$ ?

Here $\binom{n}{r}$ means $n$ choose $r$.(selecting $r$ things from total of $n$ things). I have many examples which make this statement true.

Consider $n = 2$ and $r = 2$ . $r$ divides $2$ and $2/2$ divides $\binom{2}{2}$. ($1$ divides $1$)

More example  $n = 4$ and $r = 2$ . $r$ divides $4$ and $4/2$ divides $\binom{4}{2}$  ($2$ divides $6$)

More example  $n = 6$ and $r = 2$ . $r$ divides $6$ and $6/2$ divides $\binom{6}{2}$  ($3$ divides $15$)

More example  $n = 12$ and $r = 4$ . $r$ divides $12$ and $12/4$ divides $\binom{12}{4}$  ($3$ divides $495$)

Now my question is - is this always the case? I tried proving it myself by expanding the factorials and cancelling the terms but failed to prove.

Then I tried proving it by a combinatorial proof. Then I proved it for one case.
That one case was where $n$ is even and $r = n/2$.
Then we can say $\binom{n}{n/2}$ counts the number of ways of selecting any $n/2$ things and not selecting the other $n/2$ automatically.

So consider any one such case where $A$ is set of $n/2$ selected things and $B$ is set of $n/2$ not selected things.

Then we can say there will be another case corresponding to this one where we select the $n/2$ elements in $B$ and not select the $n/2$ elements in $A$.

So these cases will be in pairs and so they will be even this proves only one case where $n$ is even and $r=n/2$.

I need help in proving this statement for all cases. How can I prove it?

答:
First we need a lemma. Denote $\nu_p(n)$ to be the greatest power in which a prime number $p$ divides $n$.

Lemma: If $\nu_p(n) = u$, then $\nu_p(n!) = \sum_{i=1}^u \frac{n}{p^i}$. This is quite trivial because you first count multiples of $p$, then multiples of $p^2$, etc.

Let $n=mr$. Let $p$ be any prime factor of $m$. We need to prove that if $\nu_p (m)=s, \nu_p(r)=t$ (note that $s\ge 1$ but $t$ can be zero), then $p^s | {n\choose r}$, or equivalently $\nu_p({n \choose r}) \ge \nu_p(m)$ . If that's the case then $m \mid $ $n \choose r$.

It's easy to see that $\nu_p(n)=s+t, \nu_p(n-r)=t$, therefore

$n \choose r$ = $\frac{n!}{r!(n-r)!} \Rightarrow \nu_p({n \choose r}) \\
= \nu_p(n!) - \nu_p(r!) - \nu_p((n-r)!) \\ = \sum_{i=1}^{s+t} \frac{n}{p^i} - \sum_{i=1}^t \frac{r}{p^i} - \sum_{i=1}^t \frac{n-r}{p^i} \\
=\sum_{i=1}^{s+t} \frac{n}{p^i} - \sum_{i=1}^t \frac{n}{p^i} = \sum_{i=t+1}^{s+t} \frac{n}{p^i} \ge \sum_{i=t+1}^{s+t} 1 = s. \blacksquare$


问:
Calculate the area between the function $\sqrt{x}$ and $x^2$ in the interval $[0 , 2]$.
Calculate the area between the function
$\sqrt{x}
$and
$x^2$
in the interval [0 , 2].

Ok,  $0<x<1$, $\sqrt{x}$$>x^2$
and  $1<x<2$, $\sqrt{x}$$<x^2$

$$ Area = \int_{0}^1(\sqrt{x}-x^2)dx + \int_{1}^2(x^2-\sqrt{x})dx$$

I know that $$ \int(\sqrt{x})dx = \frac 23x^\frac 32$$
and $$ \int(x^2)dx = \frac 13x^3 $$

So the Area is $$ \frac {10}{3} - \frac {{4}\sqrt{2}}{3} $$

Is this correct? I'm not sure if I'm doing the right thing

答:
To begin to answer your question one can first check have a graph of the equations handy, or understand that $y=\sqrt{x}$ raises faster than $y=x^2$ in the interval from $[0,1]$, after that $y=x^2$ is above the $y=\sqrt{x}$ from $[1,2]$. So know to setup the integrals:
\begin{align*}A_{\mathrm{tot}}&=A_1+A_2\\A_1&=\int_{0}^1(\sqrt{x}-x^2)dx\\A_2&=\int_1^2(x^2-\sqrt{x})dx\\ A_1&=[\frac{2}{3}x^{\frac{3}2}-\frac{x^3}3]\Bigg\vert_0^1=\frac{1}3 \\ A_2&=[\frac{x^3}{3}-\frac{2}{3}x^\frac{3}2]\Bigg\vert_1^2=\frac{9-4\sqrt2}{3}\\A_\mathrm{tot}&=\frac{10-4\sqrt{2}}{3}\end{align*}


问:
U contains a+b+c elements from A u B u C where U intersect A has at least a members, etc. U can be obtained from (A, B, C) choose (a, b, c)?
I have a number of overlapping sets. I need to choose some number of elements out of each one, with no resulting duplicates.

In this case, it is easier to choose the total number of elements from the union of all sets, and check if at least a elements are in A, at least b elements in B, etc.

My intuition wants me to beleive that this is enough to guarantee that a coloring of those elements with a colored A, b colored B, etc. is always possible. I do not need to know what that coloring is, just have a proof on hand that one exists.

Example:

A={1,2,3,4,5,6,7,8} choose 3
B={2,4,6,7,9,10} choose 2

C={3,4,5,9,11,12} choose 2

U={1,2,3,4,5,6,7} has 7 elements shared with A, 4 shared with B, and 3 shared with C. (7,4,3)>=(3,2,2). And can be colored ${1,2,3} \bigcup {6,7} \bigcup {4,5}$

答:
Given that some basic conditions are satisfied:

$\lvert A\rvert \ge a$, etc.

$\lvert A\cup B \cup C\rvert \ge a + b + c$

Then this is always possible by construction:

Pick any $a$ elements from $A$ to form $U_1 \subset A$; $\lvert U_1\rvert = a$;

Pick any $b$ elements from $B$ to form $U_2 \subset B$;

Pick any $c$ elements from $C$ to form $U_3 \subset C$.

The union $U_1 \cup U_2 \cup U_3$ may contain fewer than $a+b+c$ elements; choose enough from the remaining unpicked ones $(A\cup B \cup C)\setminus (U_1\cup U_2\cup U_3)$ to form $U$.

A colouring does NOT always exist. A counter example is

$A = \{ 1\}$; $a = 1$

$B = \{ 1\}$; $b = 1$

$C = \{ 2, 3 \}$; $c = 1$

Then the only possible choice for $U = \{ 1, 2, 3\}$ (because $\lvert A \cup B \cup C\rvert = a+b+c = 3$). Yet the $1 \in U$ needs to be coloured both $A$ and $B$, which is impossible.


问:
How do I solve $(x\cos y-y\sin y)dy+(x\sin y+y\cos y)dx=0$
$(x\cos y-y\sin y)dy+(x\sin y+y\cos y)dx=0$

ATTEMPT:

Rearranging the terms:

$(x\cos ydy+y\cos ydx) -y\sin ydy+x\sin ydx=0$

Dividing by $\cos x$ we get:

$(xdy+ydx)-y\tan ydy+x\tan ydx=0$

$ d(xy)-y\tan ydy+x\tan ydx=0$

But i am not able to simplify it further.

I also tried partial derivatives:

Let $(x\sin y+y\cos y)=M(x,y)$ and $(x\cos y-y\sin y)=N(x,y)$

This is not an exact differential equation as $\frac{\partial M(x,y)}{\partial y} \ne \frac{\partial N(x,y)}{\partial x}$

But $\frac{\frac{\partial M(x,y)}{\partial y} - \frac{\partial N(x,y)}{\partial x}}{N(x,y)}=1$ which is independent of $ x, y$.

Can i use this result to solve my problem?

答:
$$(x\cos y-y\sin y)dy+(x\sin y+y\cos y)dx=0$$
$$xd\sin y+yd\cos y+(x\sin y+y\cos y)dx=0$$
$$x(d\sin y+\sin y dx)+y(d\cos y+\cos ydx)=0$$
$$xe^x(d\sin y+\sin y dx)+ye^x(d\cos y+\cos ydx)=0$$
$$xd(e^x\sin y)+yd(e^x\cos y)=0$$
$$xd(e^x\sin y)\color{red}{+(e^x\sin y)dx-(e^x\sin y)dx}+yd(e^x\cos y)=0$$
$$d(xe^x\sin y)-(e^x\sin y)dx+yd(e^x\cos y)=0$$
$$d(xe^x\sin y)-(e^x\sin y)dx+yd(e^x\cos y)\color{red}{+(e^x\cos y)dy-(e^x\cos y)dy}=0$$
$$d(xe^x\sin y)-(e^x\sin y)dx+d(ye^x\cos y)-(e^x\cos y)dy=0$$
$$d(xe^x\sin y)-d(e^x\sin y)+d(ye^x\cos y)=0$$
Integrate:
$$xe^x\sin y-e^x\sin y+ye^x\cos y=C$$
Finally:
$$e^x(x\sin y-\sin y+y\cos y)=C$$


问:
Finding squares in finite fields
I need the definition of finding squares in finite fields and also the number of squares in a  finite field. How can we find squares in $\Bbb F_5$ and $\Bbb F_7$? (Here $\Bbb F_5$ and $\Bbb F_7$ indicate the finite fields for $q=5$ and $q=7$ respectively.)

Can we generalize for different values of $q$? I need your help.

Thank you.

答:
Hint: In a field with characteristic different from $2$, if $a\ne 0$ the equation $x^2=a$ has $0$ or $2$ solutions.

If you are interested in finding the squares in a field with $5$ elements, or one with $7$, you know what thse fields look like, square each element and list the answers you get.

Title: Finding squares in finite fields


答:
Using factorial form, it is rather easy to prove (I let you prove this part) that
$$\binom{n}{r}=\frac{n}{r}\binom{n-1}{r-1}$$

Therefore if $r$ divides $n$, then yes, $\frac{n}{r}$ divides $\binom{n}{r}$.

Title: if $n>0$ and $r>0$ ($n$ and $r$ and positive integers) and $r$ divides $n$ , then $n/r$ divides $nCr$ . Is this statement true?

Body:
if $n>0$ and $r>0$ ($n$ and $r$ and positive integers), and $r$ divides $n$, does $n/r$ divides $\binom{n}{r}$ ?

Here $\binom{n}{r}$ means $n$ choose $r$.(selecting $r$ things from total of $n$ things). I have many examples which make this statement true.

Consider $n = 2$ and $r = 2$ . $r$ divides $2$ and $2/2$ divides $\binom{2}{2}$. ($1$ divides $1$)

More example  $n = 4$ and $r = 2$ . $r$ divides $4$ and $4/2$ divides $\binom{4}{2}$  ($2$ divides $6$)

More example  $n = 6$ and $r = 2$ . $r$ divides $6$ and $6/2$ divides $\binom{6}{2}$  ($3$ divides $15$)

More example  $n = 12$ and $r = 4$ . $r$ divides $12$ and $12/4$ divides $\binom{12}{4}$  ($3$ divides $495$)

Now my question is - is this always the case? I tried proving it myself by expanding the factorials and cancelling the terms but failed to prove.

Then I tried proving it by a combinatorial proof. Then I proved it for one case.
That one case was where $n$ is even and $r = n/2$.
Then we can say $\binom{n}{n/2}$ counts the number of ways of selecting any $n/2$ things and not selecting the other $n/2$ automatically.

So consider any one such case where $A$ is set of $n/2$ selected things and $B$ is set of $n/2$ not selected things.

Then we can say there will be another case corresponding to this one where we select the $n/2$ elements in $B$ and not select the $n/2$ elements in $A$.

So these cases will be in pairs and so they will be even this proves only one case where $n$ is even and $r=n/2$.

I need help in proving this statement for all cases. How can I prove it?


问:
Find all possible Laurent expansions
What does this mean? I have a question in my book that says find all possible Laurent expansions of $f(z) = \frac{1}{(z^2-1)(z-4)}$ centered at $z=0$. I was able to break this down to a certain point, but I guess I'm confused on what it means by all possible expansions.

Here is what I have so far:

$f(z) = \frac{1}{(z^2-1)(z-4)} = \frac{1}{10} \frac{1}{z+1} - \frac{1}{6} \frac{1}{z-1} + \frac{1}{15} \frac{1}{z-4}$. Do I have to consider cases such as $|z| < 1$, $1<|z|<4$, and $4<|z|$. Or am I not understanding what the question is asking me?

For $|z|<1$ I think this is right so far, but I was able to get $\sum_{n=0}^\infty (\frac{1}{6} + \frac{(-1)^n}{10} - \frac{1}{15(4)^{n+1}})z^n$. Are the other regions I have listed all that I have left? Or are there more I'm missing out on, and is what I've done so far correct?

答:
You can fill in the details. The idea is $f(z)=\frac{1}{10}\frac{1}{z+1}-\frac16\frac{1}{z-1}+\frac{1}{15}\frac{1}{z-4}$, so in some shape or form you always want you use the geometric series formula,
$$
\sum_{n=0}^\infty z^n=\frac{1}{1-z}
$$
for $|z|<1$, but with some algebraic manipulation.

About $z=0$, the nearest singularity is at $z=1$ and $z=-1$. Starting with $|z|<1$, write
$$
f(z)=\frac{1}{10}\frac{1}{1-(-z)}+\frac16\frac{1}{1-z}-\frac{1}{15}\cdot\frac{1}{4}\cdot\frac{1}{1-\frac{z}{4}}.
$$
All geometric series are valid since $|z|<1$ so $|\frac{z}{4}|<1$.

Then in the region $1<|z|<4$, observe that if $w=\frac{1}{z}$, then $\frac14<|w|<1$ so write
$$
f(z)=\frac{1}{10}\cdot \frac{1}{z}\cdot\frac{1}{1-(-\frac{1}{z})}-\frac16\cdot\frac{1}{z}\cdot\frac{1}{1-\frac{1}{z}}-\frac{1}{15}\cdot\frac{1}{4}\cdot\frac{1}{1-\frac{z}{4}}.
$$
See if you can handle the final case. The purpose of the exercise is to think of the Laurent series in this way.

Title: Find all possible Laurent expansions


问:
What does it mean to take derivative of vector in a direction?
Suppose I have a vector field $ \vec{B} (x,y,z)$ then do $ \frac{ \partial B}{ \partial n}$ where n is the direction vector of a line denote the directional derivative of the vector in the direction of $n$?

The reason I ask is that I recently encountered this in a physics textbook but all the gradients and directional derivatives that I've seen till now were defined for scalar fields.

Edit:

The real quantity that I started with was the one from this mse post:

$$ (\nabla B_i) n_i $$

I thought this would be the directional derivative since it looked like one but then I later realized this is actually a vector field.

A picture from the book:

Page-158, I.e irodov basic laws of electromagnetism

答:
Keeping it intuitive in $\mathbb{R}^2$ and you can easily extrapolate to $\mathbb{R}^n$.

In cartesian coordinates you can write the direction vector $\vec{e_r}$ from the origin to a point in a circunference of radius $1$. Direction vectors are unit vectors.

$$\vec{e_r} = \cos(\theta)\vec{e_x} + \sin(\theta)\vec{e_y}$$

Recall that $\vec{e_x}$ and $\vec{e_y}$ are fixed in our coordinates, so they will not be affected by the derivative, but $\theta$ do. Generally, in real life problems, $\theta$ changes over implicit time $t$ such that $\theta(t)$. With this in mind we can now take the derivative of the vector $\vec{e_r}$:

$$\frac{d}{d\theta}\vec{e_r} = \frac{d}{d\theta}\cos(\theta)\vec{e_x} + \frac{d}{d\theta}\sin(\theta)\vec{e_y}$$
$$\frac{d}{d\theta}\vec{e_r} = (-\sin(\theta)\vec{e_x} + cos(\theta)\vec{e_y})\frac{d}{d\theta}\theta$$

Can you see that they are perpendicular to each other? In fact we can prove it with the dot product:

$$\vec{e_r} \cdot \frac{d}{d\theta}\vec{e_r} = -\cos(\theta)\sin(\theta) + \sin(\theta)\cos(\theta) = 0$$

Geometrically, why are they perpendicular? Consider the vector $\vec{e_r}$ for some $\theta$. It changes with infinitesimal $d\theta$ to a new position of $\theta$, say, $\vec{e_r}(\theta + d\theta)$. Note that in the limit $\vec{e_r}(\theta + d\theta) -\vec{e_r}(\theta)$ is a vector perpendicular to $\vec{e_r}(\theta)$.


问:
Solve 2nd order ODE: $\ddot{x} + a\dot{x} = b$?
How can you solve a second order differential equation of form: $\ddot{x} + a\dot{x} = b$? What type of equation is this?

答:
Second order linear differential equation.
$$\ddot{x} + a\dot{x} = b$$
Integrate directly:
$$\dot{x} + a{x} = bt+K$$
You can surely solve a first order differential equation...


问:
Showing the set {n+1/n} is closed but {1/n} is not
Let $A=\{n +1/n : n=2,3,...\}$ . I want to show that this is closed.

If we show $A^c$ is open then $A$ is closed. Here $A^c = (\cup_{i=2}^{\infty} (i +1/i, i+1 + 1/(i+1))) \cup (-\infty,2.5)$ which is an arbitaru collection of open sets which is open. This A is closed.

The only doubt I have with this style of proof is that it seems to work for $A=\{1/n\}$ as well.
Because $A^c = (\cup_{i=1}^{\infty} (1/(i+1), 1/i)) \cup (-\infty,0] \cup (1,\infty) $ <s>which is also a collection of open sets. But we know A is not closed here. Why does the argument fail here?</s>

答:
COMMENT.- We assume $A=\{n+\dfrac 1n: n=2,3...\}$ as subset of $\mathbb R$ provided with the usual topology.

The complement $A^c$ is obviously the union of open intervals $]n+\dfrac1n,(n+1)+\dfrac{1}{(n+1)}[$ and $]\infty,2+\dfrac12[$ so it is open.

For $B=\{\dfrac1n: n=2,3,....\}$ is in its "right" part a union of open intervals including $]\dfrac12,+\infty[$. However the limit $0$ of $B$ is not an element of $B$ so the "left" part of $B^c$ cannot be defined as an open interval (if you take $I_{n+1}=]-\infty, \dfrac{1}{n+1}[\space\space$ then $\dfrac{1}{n+2}\in I_{n+1}$ so $I_{n+1}$ is not a part of $B^c$).


问:
Interchanging rows in a matrix more than once before determinant
I know that people have covered the fact that changing rows will make the determinant negative, and other row operations don't affect the result, but what about interchanging the rows more than once? Does it convert it back to positive again?</p>

答:
It doesn't "make the determinant negative", it changes $D$ to $-D$.
That happens each time you interchange two rows.  So interchange them an odd number of times, you change $D$ to $-D$; interchange an even number of time, you leave the determinant unchanged.


问:
Distance to nearest integer inequality
If $\langle a \rangle$ denotes the distance from the real number $a$ to the nearest integer then why is it that for $a,b \in \mathbb{R}$ we have:

$$min \langle a \pm b \rangle \leqslant | \langle a \rangle - \langle b \rangle |$$

答:
The result you want is actually $\min \langle a \pm b \rangle \leqslant | \langle a \rangle - \langle b \rangle |$ not that both inequalities are true as that clearly implies the required inequality in the OP.

Proof: $a=m+c, b=n+d, |c| \le 1/2, |d| \le 1/2, m, n \in \mathbb Z$ then clearly $\min |c\pm d| \le 1/2$ as one can take the minus sign if $cd \ge 0$ and the plus sign if $cd \le 0$ and get the required inequality, hence $\min \langle a \pm b \rangle = \min |c \pm d|$.

But now $| \langle a \rangle - \langle b \rangle| = |c-d|$ so if $cd \ge 0$ we get equality in the required inequality as $\min |c \pm d|=|c-d|$ while if $cd <0$ then clearly $|c-d| >|c+d|=\min |c \pm d|$ (easily seen by squaring for example), so we get strict inequality. In any case, the required inequality, hence the book result is proven.

Title: Distance to nearest integer inequality


问:
Which one result in mathematics has surprised you the most?
A large part of my fascination in mathematics is because of some very surprising results that I have seen there.

I remember one I found very hard to swallow when I first encountered it, was what is known as the Banach Tarski Paradox. It states that you can separate a ball $x^2+y^2+z^2 \le 1$ into finitely many disjoint parts, rotate and translate them and rejoin (by taking disjoint union), and you end up with exactly two complete balls of the same radius!

So I ask you which are your most surprising moments in maths?

Chances are you will have more than one. May I request post multiple answers in that case, so the voting system will bring the ones most people think as surprising up. Thanks!

答:
Similar to Thomae's function, I was impressed by the Dirichlet function, which is not only discontinuous everywhere, but impossible to plot. The function is defined as:

$f(x)=\begin{cases}
  1 \mbox{ if } x\in\mathbb{Q} \\
  0 \mbox{ if }x\notin\mathbb{Q}
\end{cases}$

LastEditorDisplayName: anon

ContentLicense: CC BY-SA 2.5


问:
$P \cap N$ is a Sylow $p$-subgroup of $N$, where $N$ is normal in $G$ and $P$ is a Sylow $p$-subgroup of $G$?
In 'A Course in Group Theory' by Humphreys, Proposition 11.14 says that if $G$ is a finite group, $P$ is a Sylow $p$-subgroup of $G$ and $N$ is a normal subgroup of $G$, then $P \cap N$ is a Sylow $p$-subgroup of $N$.

But doesn't this fail in the case where $P \cap N = \{1\}$? I thought the definition of a Sylow $p$-subgroup excludes $\lbrace1 \rbrace$, since the definition of Sylow $p$-subgroup requires an order $p^n$ where $n$ is a positive integer (i.e. not zero). If not, we need to adjust the definition of Sylow $p$-subgroup to a subgroup of order $p^n$ where $n$ is non-negative. However I don't think Humphreys intends this, as in his answer to exercise 11.3 he uses $\{1\}$ as an example of a group that is not a Sylow 2-subgroup.

As an example: I think we could have $G = D_3$ (the dihedral group with 6 elements), $N = \langle a \rangle$ where $a$ is a rotation, and $P = \langle b \rangle$ where $b$ is a reflection. Then $P \cap N = \{1\}$, which is not a Sylow 2-subgroup of $N$ although $N$ is normal in $G$ and $P$ is a Sylow 2-subgroup. Please let me know what you think. Thanks

答:
This may be a bit unsatisfying, but the answer is that the Sylow $p$-subgroup of a finite group $G$ for which $|G|$ is not divisible by $p$ is simply the identity.  Note that $1$ is indeed a power of $p$ for any prime $p$, so if $p^0=1$ is the highest power of $p$ dividing $|G|$, then $\{1\}$ is the Sylow $p$-subgroup.  So, $P\cap N=1$ is not a contradition because $P$ is a Sylow $2$-subgroup of $D_3$ and $\{1\}$ is, in fact, the Sylow $2$-subgroup of $\langle a \rangle \cong C_3$.  (For an even easier example, consider $\mathbb{Z}_6$.)

If the book doesn't define this way, it's possible that the writer just forgot to write an exception to this Proposition.  This is standard in group theory literature.


问:
Finding the main argument of a solution
When solving the equation $z^3+1=-i\sqrt3$, the main argument of one of its solutions is:

a-) $\pi/3$

b-) $4\pi/9$

c-) $7\pi/9$

d-) $-2\pi/3$

I'm having trouble trying to solve the exercise because I don't really know what the question means by "main argument". Any help is welcome

答:
HINT
\begin{align*}
z^{3} + 1 = -i\sqrt{3} \Longleftrightarrow z^{3} = -1 - i\sqrt{3} = 2\left(-\frac{1}{2} - i\frac{\sqrt{3}}{2}\right) = 2\left[\cos\left(\frac{4\pi}{3}\right) + i\sin\left(\frac{4\pi}{3}\right)\right]
\end{align*}

Title: Finding the main argument of a solution


问:
Prove that a normal subgroup $K$ is characteristic in a finite group $G$ if $\gcd(|K|, |G/K|) = 1$
This is a part of an exercise $2.2$ on a page $203$ in a book "Algebra: Chapter 0" by P.Aluffi.

Let $K$ be a normal subgroup of a finite group $G$, and assume that $|K|$ and $|G/K|$ are relatively prime. Prove that $K$ is characteristic in $G$.

So we need to show that $\forall \phi \in Aut(G) \ \ \phi(K) \subseteq K$ assuming $|G| \in \mathbb{N}, \forall g \in G \ \ \ gNg^{-1} = N$ and $\gcd(|K|,|G/K|) = 1$.

Any hints?

答: For any $f\in \text{Aut}(G)$, $f(K)$ is also a subgroup, and by the second isomorphism theorem, $f(K)\cap K$ is normal in $f(K)$. Consider the group $$H=\frac{f(K)}{f(K)\cap K}=\frac{Kf(K)}{K}.$$ Then $|H|$ divides $|f(K)|=|K|$. Note that $Kf(K)$ is a subgroup of $G$, so $$|H|=|Kf(K):K|=\frac{|G:K|}{|G:Kf(K)|}.$$Thus, $|H|$ divides $|G:K|$. Therefore, $|H|=1$, so $f(K)=f(K)\cap K$, namely $f(K)\subseteq K$.


问:
$\frac{b^2-a^2}{c+a} + \frac{c^2-b^2}{a+b} + \frac{a^2-c^2}{b+c} \ge 0$ Proof
Does anyone know hot to prove this inequality?

Having: $a, b, c \gt 0$

$$\frac{b^2-a^2}{c+a} + \frac{c^2-b^2}{a+b} + \frac{a^2-c^2}{b+c} \ge 0$$

I tried with the AM-GM inequality but I couldn't get any improvement. I'm on a still point and I don't know how to continue.

Furthermore, I don't know how to get rid of the known term. I tried with the AM-HM inequality but I'm still not getting any results.

Also, just some hints would be appreciated, thanks

答:
Because
$$\sum \frac{a^2}{c+a} = \sum \frac{c^2}{c+a}.$$
Therefore, we need to prove
$$2\left(\frac{a^2}{b+c}+\frac{b^2}{c+a}+\frac{c^2}{a+b}\right) \geqslant \frac{a^2+b^2}{a+b}+\frac{b^2+c^2}{b+c}+\frac{c^2+a^2}{c+a}.$$
Suppose $a \geqslant b \geqslant c,$ then
$$a^2 \geqslant b^2 \geqslant c^2 \quad \text{and} \quad \frac{1}{b+c} \geqslant \frac{1}{c+a} \geqslant \frac{1}{a+b}.$$
Using the Rearrangement inequality
$$\frac{a^2}{b+c}+\frac{b^2}{c+a}+\frac{c^2}{a+b} \geqslant \frac{a^2}{a+b}+\frac{b^2}{b+c}+\frac{c^2}{c+a}.$$
$$\frac{a^2}{b+c}+\frac{b^2}{c+a}+\frac{c^2}{a+b} \geqslant \frac{b^2}{a+b}+\frac{c^2}{b+c}+\frac{a^2}{c+a}.$$
The proof is completed.


答:
It's a second order nonhomogeneous linear equation with linear coefficients. Since it's linear, you can split it into homogeneous and particular solutions. For the homogeneous solution, you can take $D$ as the differential operator, and then the equation is $D^2x+aDx = 0$ or $(D^2+aD)x=0$. This factors into $D(D+a)x =0$. If $Dx = 0$, $x=C_1$. If $(D+a)x =0$, then $x = C_2e^{-at}$. This gives the homogeneous solution $x = C_1+C_2e^{-at}$.

For the particular solution, we can take the general polynomial $p(t)=c_0+c_1t+c_2t^2$ and require $p''+ap'=b$. The RHS has no $t$ term, and $p''$ has no $t$ term, so $p'$ must have no $t$ term, which mean that $p$ has no $t^2$. That means that $p''$ is zero, so $ap'=b$, and hence $p = \frac b a t$ (we don't need the constant when we do the indefinite integral, since that's already in the homogeneous solution).

Combining the homogeneous and particular solutions, we get $x = C_1+C_2e^{-at}+\frac b a t$

Title: Solve 2nd order ODE: $\ddot{x} + a\dot{x} = b$?

Body: How can you solve a second order differential equation of form: $\ddot{x} + a\dot{x} = b$? What type of equation is this?


问:
Simultaneous Equations
How do I solve these simultaneous equations using an algebraic method?
\begin{align}
3x + 6y & = 30\\
x + 6y & = 20
\end{align}

It's on a old test paper and I'm kind of doing revision...

I was thinking of doing $30 - 20 = 10$. I don't know what to do after? We haven't done simultaneous questions yet in class but I'm trying to work it out myself. Can you give any hints or a formula?

Could I do trial and error? But I don't want to do that, I want to know the method.

答:
$$3x + 6y = 30\tag{1}$$

$$\;x + 6y = 20\tag{2}$$

Subtracting term for term $(2)$ from $(1)$ gives us $$(3x + 6y) - (x + 6y) = 30 - 20\tag{3}$$ $$3x - x + 6y - 6y = 10,\; $$ (Very nice, since we eliminate $y$!) Now we can solve the resulting equation for $x$

$$2x + 0\cdot y = 10 \implies x = 5$$

Now just solve for $y$, using, say, equation $(2)$: $$x + 6y = 20\;\;\text{and} \;\;x = 5 \implies 5 + 6y = 20$$ $$ \implies 6y = 20 - 5 \implies 6y = 15 \implies y = \frac {15}{6} = \frac 52$$

$$x = 5 \quad \text{and }\quad y = \frac 52$$

Title: Simultaneous Equations


问:
Prove an ODE has asymptotically stable equilibrium point.
I am given the ODE
$$\dot{x}=-f(x)$$
( $\dot{x}=\frac{dx}{dt}$ with $x$ being a function of $t$)

with
$$f(0)=0$$
$x \in \mathbb{R}$

such that $f$ is locally Lipschitz on $(-a,a)$, $a >0$

and $xf(x) >0$ for all $x \in (-a,a)- \{0\}$

Prove that $0$ is an asymptotically stable equilibrium point of the ODE.

I tried the following
$$\dot{x} x =-  f(x)x $$
$$\frac{x^2}{2} = -\int_0^x f(y)ydy$$
and take $$V(x)=\frac{x^2}{2} + \int_0^x f(y)ydy$$ as a Lyapunov function. Now $f(x)x >0$ so $V(x) >0$
Also it's clear that $V(0)=0$ be
So $V(x)$ is positive defined.

And this is where I am stuck, for 0 to asymptotically stable then $V^*(x) := \frac{dV}{dt}$ must be negative defined, but I can't see why this is.
How can I prove this?

答:
The Lyapunov function is $V(x)=x^2/2$. Its derivative

$$
\dot V= x\dot x= -xf(x)
$$
is negative definite.


问:
How to obtain equation from graph?
Consider we have an autonomous differential equation
$$\dfrac{dy}{dt}=f(y)$$
and we need to draw a slope field using the information from this graph:

I know how to sketch this by hand, but I am trying to sketch it using a software and I want to know if it was possible to know what is the equation $f(y)$ from just looking at this graph. All I can see is that we have four equilibrium points: $y=-4$, $y=-2$, $y=1$ and $y=4$.

And we can also tell for what values of $y$ the function $f(y)$ is either positive or negative.

I tried
$$f(y)=(y+4)(y+2)(y-1)(y-4)$$
but it did not give me the correct slope field. Would it be possible to figure the equation of $f(y)$ out? Or is the only way to sketch it is by hand?

答:
If all you have is this graph, then it would be impossible to be sure one has the right formula. Since the derivative is not continuous, it would look like

if $x<2$ then $f(x)=\;$some nonlinear function
if $x>2$ then $f(x)=ax+b$

Title: How to obtain equation from graph?


答:
You are correct about your guess $f()=(+4)(+2)(−1)(−4)$ for the left hand side of the graph when $y\leq 2$. However, we need to scale this by some constant $c$, so really we have $f()=c(+4)(+2)(−1)(−4)$.

For the right hand side when $y\geq 2$, we can see we have something like $f(y)=d(4-y)$ where $d$ is some constant. I hope this helps.

Title: How to obtain equation from graph?

Body:
Consider we have an autonomous differential equation
$$\dfrac{dy}{dt}=f(y)$$
and we need to draw a slope field using the information from this graph:

I know how to sketch this by hand, but I am trying to sketch it using a software and I want to know if it was possible to know what is the equation $f(y)$ from just looking at this graph. All I can see is that we have four equilibrium points: $y=-4$, $y=-2$, $y=1$ and $y=4$.

And we can also tell for what values of $y$ the function $f(y)$ is either positive or negative.

I tried
$$f(y)=(y+4)(y+2)(y-1)(y-4)$$
but it did not give me the correct slope field. Would it be possible to figure the equation of $f(y)$ out? Or is the only way to sketch it is by hand?


问:
How do ring morphisms work when dealing with polynomial rings?
I've been trying to understand how ring morphisms work when dealing with polynomial rings, but I'm having a little bit of trouble understanding how they work.

Let $R,S$ be rings (they need not be commutative nor have a multiplicative identity) and $f:R\to S$ a ring morphism. We know that this induces a ring morphism $f^*:R[x]\to S[x]$ given by $f^*(a_0+a_1x+\cdots+a_nx^n)=f(a_0)+f(a_1)x+\cdots+f(a_n)x^n$. My problem now is: is every ring morphism $F:R[x]\to S[x]$ of the form $F=g^*$ for some $g:R\to S$?

I don't know whether it is or not the case, but if it is I'm having trouble proving it.

My first approach would be that any polynomial can be thought as a sum and product of constant polynomials and $x^k$ for some $k$ and in that sense, then $F(a_0+\cdots a_nx^n)=F(a_0)+\cdots F(a_n)F(x)^n$, so if I knew that $F$ sends constant polynomials to constant polynomials and polynomials of the form $x^n$ to themselves, then I would have the desired result, but this is something I haven't been able to prove yet.

Only thing I know is that for $c\in R$, $F(c)=b_0+\cdots+b_mx^m$ with $b_i\in S$ for all $i$, but I can't deduce from there that $b_i=c$ if $i=0$ and $b_i=0$ otherwise. Same case with $x^n$ .

If this is not the case, however, and I'm trying to prove something false, then how do these morphisms work? Is there a way to more or less understand their behaviour?

Any help is thanked for :)

答:
A ring homomorphism $F : R[x] \to S[x]$ can send $x$ to any element of $S[x]$; for a particular value of $F(x)$, the image of the coefficient ring $F(R)$ must land in the centralizer $Z_{S[x]}(F(x))$ of $F(x)$. This is a complete description of all possible ring homomorphisms. Equivalently, $F$ can restrict to an arbitrary ring homomorphism $R \to S[x]$, and then $F(x)$ must commute with the image.

This construction simplifies a lot if $R$ and $S$ are commutative; then $F(x)$ is any element of $S[x]$ and $F(R)$ can be arbitrary. So your morphisms are less than fully general for two reasons:

$F(R)$ need not be contained in $S$, and may contain non-constant polynomials, and

$F(x)$ need not be $x$, but can in fact be any element of $S[x]$ in general.


答:
Subtract the two equations. We then get
$$\color{red}{(3x+6y)} - \color{blue}{(x+6y)} = \color{red}{30} - \color{blue}{20} \implies (3x-x) + (6y-6y) = 10 \implies 2x = 10 \implies x = 5$$
Now plug in $x=5$ in one of the equations, say in the equation $\color{blue}{(x+6y) = 20}$. We then get that
$$5+6y = 20 \implies 6y = 15 \implies y = \dfrac{5 \times3}{2 \times 2} = \dfrac52$$</p>

Title: Simultaneous Equations

Body:
How do I solve these simultaneous equations using an algebraic method?
\begin{align}
3x + 6y & = 30\\
x + 6y & = 20
\end{align}

It's on a old test paper and I'm kind of doing revision...

I was thinking of doing $30 - 20 = 10$. I don't know what to do after? We haven't done simultaneous questions yet in class but I'm trying to work it out myself. Can you give any hints or a formula?

Could I do trial and error? But I don't want to do that, I want to know the method.


问:
linear programming minimum problem
A construction company has 6 projects, for each they need $d_i$ workers. The company has no workers at the beginning of project 1.

Each new worker must take a safety course that costs 300, and 50 more for each worker.
If there is no new worker there is no course.

Firing a worker does not cost any money, and a workers can't be rehired.

Given that the salary of a worker is 100 per project, formulate a linear programming problem that minimizes the workers costs.

What I tried:

Let $x_i$ be the number of new workers for project $i$.

Let $y_i$ be the number of old workers remaining from previous projects until project $i$ (all the workers hired - all the workers that were fired)

Let $z_i$ be an indicator such that $z_i =0 \iff x_i>0$

The function I'm trying to solve is:

$\min(\sum_{i=1}^6 150x_i + 300(1-z_i) + 100y_i)$

s.t:
\begin{align}
x_i,y_i,z_i &\ge 0 \\
z_i &\ge 1-x_i \\
y_i + x_i &\ge d_i \\
y_i &\ge y_{i-1} + x_i
\end{align}

Something feels not right to me. The main reason is that I tried to use matlab to solve this and it failed.

What did I do wrong? How can I solve this question?

答: Seems correct except that the last constraint should instead be $y_i \le y_{i-1} + x_{i-1}$.

Title: linear programming minimum problem


答:
Note that every coefficient in the first equation is a multiple of $3$, so you can divide through by $3$ and replace $3x+6y=30$ with the equivalent equation $x+2y=10$. You now have the system

$$\left\{\begin{align*}
&x+2y=10\\
&x+6y=20\;.
\end{align*}\right.$$

Now it’s very apparent that if you subtract the top equation from the bottom one, you’ll get an equation that does not contain $x$:

$$(x+6y)-(x+2y)=20-10\;,$$

or, after simplification,

$$4y=10\;.$$

You can easily solve that for $y$ and then substitute the result back into either of the original equations and solve the resulting equation for $x$.

Even if the coefficients in the first equation had not all been multiples of $3$, I could have used this approach. Suppose that the first equation had been $3x+5y=32$; dividing through by $3$ would have left me with the system

$$\left\{\begin{align*}
&x+\frac53y=\frac{32}3\\\\
&x+6y=20\;,
\end{align*}\right.$$

and I can still subtract one equation from the other to get a single equation without $x$ in it. The arithmetic is a little messier, but the principle is exactly the same and can be applied to any system of this kind.

Title: Simultaneous Equations