TITLE: Homologically nice commutative rings
QUESTION [11 upvotes]: Let $R$ be a commutative regular local ring. Is it true that for every $\mathfrak p \in \mathrm{Spec}(R)$ there is a finitely generated $R$-module $M$ such that $\mathrm{projdim}(M)=\mathrm{ht}(\mathfrak p)$ and $\mathrm{Ass}(M)=\{\mathfrak p\}$?
Or is there some family of commutative noetherian rings where is this true?

I know that this holds if $R$ is commutative regular local of Krull dimension $\leq 4$ (up to dimension 3 it was easy, because factor rings $R/\mathfrak p$ where always CM, so we can take $M=R/\mathfrak p$. Dimension 4 was harder and in dimension 5 or more I don't know).
Is this an easy/hard/hopeless/already open/similar to something problem?
Thanks,
David

REPLY [7 votes]: OK, so this is weaker than your last question, which is false but related to some open problems and also weaker than the conjecture in your first question which is another famous open problem. All of these sound like a nice project (-:.
The short anwser is this one is also open in general. I will show that your statement, if true for all regular local ring, would imply one of the outstanding open problem, the so-called Serre's Positivity conjecture. I will sketch the proof below.
Suppose your statement is true for any regular local ring $(R,m)$. Let $p,q$ be such that $\sqrt{p+q} =m$ and $\dim R/p + \dim R/q = \dim R$. By your statement, we can choose Cohen-Macaulay module $M,N$ such that $Ass(M)= \{p\}$ and  $Ass(M)= \{q\}$. Let:
$$\chi(M,N) = \sum_{i\geq 0} (-1)^i\text{length}(\text{Tor}_i^R(M,N))$$
the Serre's intersection multiplicity.
Then $M\otimes N$ has finite length and $M,N$ are Cohen-Macaulay,  and  a classical result by Serre (can be found in his book Local Algebra, V.6, Theorem 4, p 110 of the English version) says that $\text{Tor}_i^R(M,N)=0$ for $i>0$, so
$$\chi(M,N) =\text{length}(M\otimes N)>0$$
(This is a nice generalization of Bezout theorem, since curves are Cohen-Macaulay)
But since $Ass(M)= \{p\}$ one has a prime filtration of $M$ by $a>0$ copies of $p$ and primes of smaller dimensions. Similarly $N$ has a filtration with $b>0$ copies of $q$ and primes of smaller dimensions. As $\chi$ is additive on short exact sequences, one has:
$$\chi(M,N) = ab\chi(R/p,R/q)$$
(one needs to use the Vanishing part of Serre's conjectures, which is known, here)
So one can conclude that $\chi(R/p,R/q)>0$! But this has been open for about 50 years, so I doubt your statement is known (for all regular local rings).


TITLE: Which has a higher order of growth, n! or n^n?
QUESTION [8 upvotes]: In our algorithms class, my professor insists that n! has a higher order of growth than n^n. This doesn't make sense to me, when I work through what each expression means.
n! = n * (n-1) * (n-2) * ... * 2 * 1
n^n = n * n * n * n * ... * n * n

Since n is, by definition, greater than n -1 or n-2, shouldn't any n^n, which is the product of n number of n's, be greater than n!, which is the product of an n number of integers less than n?

REPLY [7 votes]: "Higher order of growth" does not mean that $n!\lt n^n$ but the stronger property that
$$n!/n^n\to0.$$
To prove that this property holds, note that $n\geqslant2k$ for every $1\leqslant k\leqslant n/2$ and $n\geqslant k$ for every $n/2\lt k\leqslant n$, hence
$$
n^n=\prod_{k=1}^{n}n\geqslant\prod_{1\leqslant k\leqslant n/2}(2k)\cdot\prod_{n/2\lt k\leqslant n}k=2^{n/2}\cdot n!,
$$
which proves that
$$
\frac{n!}{n^n}\leqslant\frac1{2^{n/2}}\to0.
$$
Thus, indeed $n^n$ has a higher order of growth than $n!$, not the opposite.


TITLE: Sequences and inequalities in $\mathbb{R}^n$
QUESTION [1 upvotes]: Let $x_k,y_k$ be sequences in $\mathbb{R}^n$ with $\lim x_k=a$, $\lim y_k=b$ and $$|x_k-b|<r<|y_k-a|$$ prove that $|a-b|=r.$
My attempt was:
We can write $|x_k-b+(a-a)|=|x_k-a+(a-b)|$ and $|y_k-a+(b-b)|=|y_k-b +(b-a)|$. My first question is: In $\mathbb{R}$ we can write $|u|-|v|\leq |u-v|$, can we do $$|x_k-a|-|b-a|\leq |x_k-a-(b-a)| ?$$
if we can, we have $$|x_k-a|-|b-a|<r<|y_k-b|+|b-a|$$
and $|x_k-a|<\epsilon,|y_k-b|<\epsilon.$ So we can write $$\epsilon-|b-a|<r<\epsilon +|b-a|$$ This was my last "step". I can't see how can i conclude that $|b-a|=r.$

REPLY [2 votes]: Your second last and last inequalities are true but not useful. Instead you want to use triangle inequality at the second last inequality as follows:
$|b-a|-\epsilon < |b-a|-|x_k-a|<r < |y_k-b|+|b-a|< |b-a|+\epsilon\implies |r-|b-a||<\epsilon\implies r = |b-a|$ since it is true for any $\epsilon > 0$.


TITLE: The kernel of a the projection of vector into $xy$-plane
QUESTION [2 upvotes]: Let $F:R^3 \rightarrow R^3$ be the projection of a vector $v$ into the $xy$-plane of the form $(x,y,0)$, that is$$F(x,y,z) = (x,y,0)$$
Then the kernal of F is the z-axis, that is points of the form (0,0,c). That is $$Ker\; F = \{(a,b,c): a=0, b=0\} = z-axis$$
I don't understand why it is $(0,0,c)$ instead of $(0,0,0)$?
Because as far as I understand that kernel takes everything to the zero point which is something like $F(v)=0$ and here in this case, shouldn't it be $(0,0,0)$? And also, this is the projection onto the $xy$-plane, if it is on the z-axis, it no longer stays on the $xy$-plane.
I am really confused.

REPLY [0 votes]: Given $F: \mathbb{R}^3 \to \mathbb{R}$ then $\textbf{Ker}(F) = F^{-1}(\vec{0}) = \{(0,0,c)\} \Rightarrow a = b = 0$.


TITLE: Theorem on Functions
QUESTION [0 upvotes]: So, I'm trying to prove this particular theorem from Vladimir Zorich's Mathematical Analysis I. It's stated as follows:
Let $f:X \rightarrow Y$ and $g:Y \rightarrow X$ be functions. Then, $ (g \circ f = e_X) \implies$ (g is surjective) $\land$ (f is injective). $e_X$ is the identity mapping from X to X.
I was wondering if someone could check my proof and see if it works or not.
Proof
Let us construct $g \circ f$ as a set. This is done as follows:
$ g \circ f = \{ (x,x) \in X^2 : \exists y \in Y: ((x,y) \in f) \land ((y,x) \in g)\}$
Clearly, there are two statements that are being made here:
$\forall x \in X: \exists y \in Y: (y,x) \in g$
$\forall x \in X: \exists y \in Y: (x,y) \in f$
The first proposition implies that g is surjective, since the definition of surjectivity demands that there exist at least one input for every output.
Now, suppose that f is not injective. Then, the following proposition must be true:
$\exists x_1,x_2 \in X: [(x_1,y) \in f] \land [(x_2,y) \in f] \land (x_1 \neq x_2]$
Thus, there exists a $y \in Y$ such that $(x_1,x_2) \in g \circ f \land x_1 \neq x_2$. This is a contradiction, since $g \circ f$ is the identity mapping. Hence, f must be injective. This completes the proof.

Vladimir Zorich does provide a proof in the textbook, by the way, and i do understand that proof. However, the above is just my attempt at proving the theorem before I saw his proof. I'm trying to get into the habit of proving things on my own before seeing the actual proof done by the author.

REPLY [1 votes]: So you want to show if $(g \circ f)=e_X$ then ($g$ is onto and $f$ is 1-1).
If $x \in X$ then $g(f(x))=x$ by assumption, so $x$ has a pre-image in $Y$ ($f(x)$) and so $g$ is onto.
If $f(x_1) = f(x_2)$ then $$x_1 = g(f(x_1)) = g(f(x_2)) = x_2$$ and so $f$ is 1-1.
This seems much simpler to me.


TITLE: How many 9-digit numbers are there with twice as many different odd digits involved as different even digits.
QUESTION [2 upvotes]: How many 9-digit numbers are there with twice as many different odd digits
involved as different even digits (e.g., 945222123 with 9, 3, 5, 1 odd and 2, 4
even).
(5c1)(5c2)3^9 +(5c2)(5c4)6^9+(5c3)(5c6)9!
even:0 2 4 6 8
odd:1 3 5 7 9
pick out the even one first
then pick out odd , then order them
is that correct?
i think im missing the situation that the number cannot start with 0.

REPLY [3 votes]: You’re right in thinking that the number of distinct odd digits cannot be more than $3$. You’re also right in thinking that there are $\binom51\binom52$ ways to choose one odd digit and two even digits, $\binom52\binom54$ ways to choose two odd and four even digits, and $\binom53\binom56$ ways to choose three odd and six even digits, but you should notice that $\binom56=0$: you can’t pick $6$ different even digits when only $5$ are available. Thus, there are really only two cases to consider: one odd digit and two even digits, and two odd and four even digits. The real work, though comes in counting the ways to arrange the digits once you’ve chosen them.
Suppose that you’ve chosen an odd digit, $d$, and two even digits, $e_0$ and $e_1$. If you use $d$ only once, you can put it in any of $9$ positions in the number. Then you can distribute $e_0$ and $e_1$ in the other $8$ positions however you please, except that you cannot use just $e_0$ or just $e_1$. There are $2^8$ ways to distribute $e_0$ and $e_1$ among the $8$ open positions, but two of those use only one of the digits, so there are $2^8-2$ ways that use both digits. Thus, we get a total of $9(2^8-2)$ nine-digit numbers in this subcase. If you use $d$ twice, there are $\binom92$ pairs of positions in which you can place the two $d$’s, and by the same reasoning as before there are $2^7-2$ ways to distribute $e_0$’s and $e_1$’s amongst the remaining $7$ places, so there are $\binom92(2^7-2)$ nine-digit numbers in this subcase. Continuing in this fashion, it’s a little tedious but not hard to get the number of nine-digit numbers in this case.
If instead you’ve chosen odd digits $d_0$ and $d_1$ and even digits $e_0,e_1,e_2$, and $e_3$, you can reason similarly, though there’s a little more work involved. Suppose, for instance, that you’ve decided to put the odd digits into $4$ spots, leaving the other $5$ for the even digits. There are $\binom94$ ways to choose the $4$ positions for the odd digits. There are $2^4-2$ ways to distribute $d_0$ and $d_1$ amongst these $4$ positions, excluding the two ways that use only one of the two digits. It remains to count the ways to distribute the even digits amongst the other $5$ positions. Clearly one of them must appear twice and the other three once each. There are $4$ ways to pick the one that appears twice, and there are $\binom52$ ways to pick the slots for it. There are then $3!$ ways to permute the remaining $3$ even digits amongst the remaining three slots, for a grand total of $\binom94(2^4-2)\cdot4\binom52\cdot3!$ numbers. There a few more subcases, depending on how many places you fill with odd digits, but you can use the same basic ideas for all of them.


TITLE: what is a measurable set
QUESTION [1 upvotes]: I have a question about the meaning of measurable set.
I was reading that if given a space say $\Omega$ and a sigma algebra say $X$ for that space then we call  $(\Omega, X)$ a measurable space. So does it mean we call $\emptyset$, $\Omega$ measurable set (how about the other sets inside that sigma algebra, do we all them measurable set as well?) and if say $E$ is one of the set in $X$ being measurable, does it  mean we also say $E^c$ is measurable...?  my question is "is it correct to automatically say all the sets in $X$ are measurable"?
Do we have to worry about the mapping say $F$: $X \longrightarrow Y$, do we have to care about what $F$ is in order to say whether the set in the sigma algebra $X$ are "measurable" or not?
The reason I am asking this question is because when I was reading the "accepted answer" to this question here:
Why the characteristic function is measurable?
the person who answer the question says this:
$X_E^{-1}(\{0\}) = E^c$ is perfectly measurable.
My question is where is the "perfectly measurable" assumption arrived from?
is it automatic that if say a set called $E$ is measurable (in a sigma algebra), then it automatically mean $E^c$ is measurable? how about the set of $\emptyset$, and the set of $\Omega$?  are the also considered as "automatically measurable"?
My question I guess is how does that person who answered that question say "perfectly measurable", is it just by definition?
Could someone explains?

REPLY [0 votes]: In order to a triple $(\Omega, \mathcal{A}, \mu)$ be a measurable space, the measure $\mu$ must be defined for every set in $\mathcal{A}$. The reason we need such a $\sigma$-algebra is exactly to distinguish the measurable sets (i.e., the ones in $\mathcal{A}$) of the non-measurable sets.


text:
\section{Conclusions}
\label{sec:conc}

We have introduced a new framework called \emph{approximation-tolerant model-based compressive sensing}. Our framework consists of a range of algorithms for model-based compressive sensing that succeed even when the model-projection oracles are approximate.  All our algorithms involve oracles that provide constant-factor approximations to both the ``head'' and ``tail'' versions of the model-projection problem. We have instantiated these algorithms for the Constrained Earth Mover Distance (CEMD) model. To achieve this, we have designed novel polynomial-time head- and tail-approximation oracles for the CEMD model based on graph optimization techniques. Leveraging these oracles and our framework results in nearly sample-optimal recovery schemes for signals belonging to this model.

Several avenues for future work remain. We have developed model-based recovery schemes that succeed with dense measurement matrices (AM-IHT, AM-CoSaMP), as well as sparse matrices (AM-IHT with RIP-1). An interesting question is whether model-based recovery can be extended to other classes of measurement matrices, such as subsampled Fourier matrices~\cite{RV08}. Also, the required sample-complexity $m$ specified by Theorem~\ref{thm:recovery} is a factor of $ \log(\frac{B}{k} \log\frac{k}{w})$ away from the optimal $m = O(k)$, and it is possible that a different approach is needed to remove this log-factor. Finally, finding an efficient algorithm (or proving a computational hardness result) for \emph{exact} projections into the CEMD model remains an open question.

config: arxiv


TITLE: Precise interpretation of the p-value
QUESTION [0 upvotes]: At the intuitive level, we know the p-value to be result that is at least as extreme as we've seen. For example, flipping a coin 20 times and observing 14 heads when our null hypothesis is that P(heads) = 0.5. We find that the p-value is sum of the probabilities from 14 to 20 heads : P(X >= 14) = 1 - P(X<= 13) = 1-binomcdf(20, 0.5, 13) = 0.057 where binomcdf represents the binomial cumulative distribution function of a random variable X (in this case the # of successes of heads) less than or equal to X = x. When we use the two tailed test we find that 2(0.057) = 0.1153 which exceeds an arbitrary level of significance at alpha = 0.05. This tells us that we fail to reject the null hypothesis at the 5% level.
Is it correct to say that 90% of the time "we are certain" that the coin will flip within two or more standard deviations away from the mean? Why couldn't I just say 100 - 0.1153 = 99.9% of the time "we are certain" that the coin will flip within two or more standard deviations away from the mean?

REPLY [1 votes]: Is it correct to say that 90% of the time "we are certain" that the coin will flip within two or more standard deviations away from the mean?

No, because given the same information (14 Heads) you should tell you one thing only. You cannot be certain "90% of the time" for something that just happened (14 heads). There is only one "time", and it is "now". (just like you cannot say "This morning, 90% of the time, I will have coffee" -- it makes not sense, you either have coffee this morning or you do not).
Note : Moreover, the standard deviation for 20 draws of a fair coin is
$$\sqrt{20\times 1/2\times(1-1/2)}=2.236,$$
thus $2\,\sigma$ is not integer (this is not a continuous distribution). Actually, being $2\sigma$ away from 10 is the same as being $\leq5$ or $\geq15$ which is 0.0413895 (as per binomial)... but this is true only IF the coin is fair. If the coin is not fair you CANNOT compute this probability (knowing that the coin is not fair does not mean you know its frequency of Heads, just that it is not 1/2).
But you do not know for sure if the coin is fair and, as a matter of fact, you will never be certain 100% that it is (or that it is not). Any coin, fair or not can turn 14 Heads (unless it has two Heads or two Tails of course). That's life!
Back to the p-value which means this, and only this : "IF the null hypothesis were true (fair coin, absolutely certain, 100% sure), there would be a probability $p$ of getting such an extreme observation" (for 14 Heads, p=11.53%). In spite of the way the p-value is often interpreted as a level of confidence or trust (or even worse, a probability of something being true), it is not the case.
The usual mistake about the p-value is confusing
$$p=P(\text{ extreme observation }\,| \ H_0)$$
with some "probability" that the coin is fair, i.e.,
$$P(H_0\,|\,\text{extreme observation}).$$
Think about the following situation : you got your coin examined by a physicist who tells you with pretty much 99,999% "certainty" that your coin will, in the long run, fall on H say 80% of the time (or whichever other probability you can imagine as long as it is neither 0 nor 1). Still, you do the test, get 14 Heads (it can happen) and get that p-value of 11.53% -- you cannot reject $H_0$ (fair coin). What do you think is going on? Either the physicist was right, $H_0$ IS wrong, and your experiment is unlucky enough that you fail to reject $H_0$, OR the physicist (which you should trust way more than a simple 20-toss experiment) was wrong, the long-term frequency is anything but 80%, and your experiment teaches you nothing (remember that "failing to reject" is NOT equivalent to "accept $H_0$".
There is quite a bit of discussion on the relevance of the p-value in experimental research. If you are interested this paper is a good starting point:
Cohen. The Earth Is Round ($p<0.05$)


TITLE: When is a log-convex function convex?
QUESTION [3 upvotes]: I consider the one-dimensional real axis. A function $f$ defined on the axis is log-convex if $f(x)f''(x)\ge (f'(x))^2$ for all $x\in\mathbb{R}$. I know that a convex function may not be log-convex, i.e., $f(x)=x$ and $f(x)=x^2$.
I also know that for log-concavity, a non-negative function that is concave is also log-concave, as $f(x)f''(x)\le 0\le (f'(x))^2$. Similarly I wish to know the conditions on a convex function that make it log-convex.

REPLY [4 votes]: (Log-)convex functions do not need to be twice differentiable, so any proof through $\frac{d^2}{dx^2}$ lacks generality.
On the other hand $e^x$ is both a convex and log-convex function, and we may wonder when the composition of two convex functions is convex. Assume that $f(x)$ is convex . Then $g(x)=e^{f(x)}$ is convex iff
$$ g(\lambda x+(1-\lambda) y) \leq \lambda g(x) + (1-\lambda) g(y)\qquad \forall \lambda\in[0,1] $$
which is equivalent to
$$ \exp\left[f(\lambda x+(1-\lambda) y)\right]\leq \lambda e^{f(x)}+(1-\lambda)e^{f(y)}\qquad \forall\lambda\in[0,1]. $$
By the convexity of $f$ we know that $f(\lambda x+(1-\lambda) y)\leq \lambda f(x)+(1-\lambda)f(y)$. Since $\exp$ is increasing we get
$$ \exp\left[f(\lambda x+(1-\lambda) y)\right]\leq \exp\left[\lambda f(x)+(1-\lambda)f(y)\right] $$
unconditionally, and since $\exp$ is convex we get
$$\exp\left[\lambda f(x)+(1-\lambda)f(y)\right]\leq  \lambda e^{f(x)}+(1-\lambda)e^{f(y)}$$
as wanted. In other terms, if $a(x),b(x)$ are convex functions and $a(x)$ is (weakly) increasing, then $(a\circ b)(x)$ is a convex function, as shown here, too. It follows that any log-convex function is also convex, as the exponential of a convex function.
In general nothing can be said about the composition of a concave function (like $\log$) with a convex function. If we take $f_1(x)=x^2, f_2(x)=e^{x^2}, f_3(x)=x e^{x\sqrt{x}}$, then over $\mathbb{R}^+$ we have that $f_1,f_2,f_3$ are convex but $\log f_1$ is concave, $\log f_2$ is convex and $\log f_3$ is neither convex or concave.

REPLY [3 votes]: A log convex function is always convex. Let $g$ denote $\log(f)$ so $e^g = f$. The function $e^g$ is convex if $g$ is convex. (Show that $e^{f(x)}$ is convex.)
In the case when $\log f$ is twice differentiable it is easy to show:
$f'' = (e^g)'' = e^g(g'' + (g')^2) \geq 0$
where the inequality follows from the nonnegativity of a convex functions second derivative.
For the case when $f$ is convex we have that
$g'' = \frac{f f'' - (f')^2}{f^2} \propto f f'' - (f')^2$ so
$g''$ is positive whenever $f \geq \frac{(f')^2}{f''}$.
Further,
$g(\lambda x + (1 - \lambda)y) \leq \log(\lambda f(x) + (1-\lambda)f(y))$ since $f$ is convex.
Thus $g$ is convex whenever
$$
\log(f(\lambda x + (1-\lambda)y))
\leq \lambda \log f(x) + (1-\lambda)\log f(y) = \log f(x)^\lambda f(y)^{1 - \lambda}
$$
Taking the exponent on both sides gives the condition
$$
f(\lambda x + (1-\lambda)y) \leq
f(x)^\lambda f(y)^{1 - \lambda}.
$$
To get a simple necessity condition, we can consider the special case $\lambda = 0.5$ to get that
$$
f^2(\frac{x+y}{2}) \leq f(x)f(y).
$$
is a necessary but not sufficient condition. Setting $y=x+2a$ gives another interesting necessary condition: $f(x + a)f(x + a)\leq f(x)f(x+2a)$.


TITLE: How to compute the intercept of a square with a line given by two points?
QUESTION [0 upvotes]: Suppose I have a point in a square, with side length s and two sides along the x/y-axes, not necessarily the center, and a point outside of the square. What is a function that computes the intercept between the sides of the square and the line given by those two points? I'm having trouble with the inherent piecewise nature of the problem, since the four lines are different, and I need this for some code.

REPLY [0 votes]: Alright let's start with some definitions:
$s$ is the side length of the square (which is centered at $(0, 0)$).
$(x_1, y_1)$ is the point inside the square.
$(x_2, y_2)$ is the point outside the square.
$(x_i, y_i)$ is the point of intersection.
I'm not going to explicitly answer everything for you, but I'll give you some hints. First, think of this as an extension of finding the $x$-intercept or $y$-intercept of a curve. To do that, you set $y$ or $x$ (respectively) to be $0$. How can that be related to a line with a square?
It is also helpful to know the equation of the line:
\begin{align}y - y_1 &= m(x - x_1)\\
(x_2-x_1)(y-y_1)&= (y_2-y_1)(x-x_1)\end{align}
So what I would do is check the intercepts of this line with the "axes" of the square, and if they lie within the piecewise constraints (e.g. $0<x<s$), there's your answer. Just be careful for lines going through the corner of the square and if $\Delta x$ or $\Delta y$ is 0. If you're still confused, I can give some more hints.


TITLE: Maximum size of a minimal vertex cover
QUESTION [3 upvotes]: Given a graph or hypergraph $G$ with vertex set $V(G)$ and edge set $E(G)$, a vertex cover is a set of vertices $C\subset V(G)$ such that every edge contains at least one vertex in the set $C$. $C$ is a minimal vertex cover if it is no longer a vertex cover after removing any element $c\in C$.
The minimum vertex cover problem, which asks for the smallest cardinality of such a set, is NP-hard. What about the complexity of finding the largest minimal vertex cover? And/or the decision problem of whether there is a minimal vertex cover of cardinality at least $k$?
As a very small example, consider a path on 5 vertices.
$v_1$ ------ $v_2$ ------- $v_3$ ------- $v_4$ ------ $v_5$
The maximum size of a minimal vertex cover in this graph is 3: the sets $\{v_1,v_3,v_5\}$ and $\{v_2,v_3,v_5\}$ are two examples that achieve this. Notice by the second example that these are not necessarily independent sets.
I'm interested in how to find maximum minimal vertex covers, but equally interested in determining or bounding the value of the maximum cardinality, without necessarily producing the sets.
The answer to this question mentions the idea of a maximum minimal vertex cover, but doesn't say anything about computing such a thing. I was unable to find another discussion of the subject.

REPLY [1 votes]: One can encode this problem as a maximum-cost propositional SAT problem.
Let there be a propositional variable $x_v$ for each vertex $v$ in the graph. There are two types of constraints:

Covering constraints: for each edge $(u,v)$, one endpoint must be included.  That is, $x_u \vee x_v$ must hold.
Minimality constraints: suppose vertex $v$ has neighbors $u_1,\ldots, u_k$; $v$ can be removed if and only if all its neighbors are included in the cover.
The constraint for $v$ is therefore $\neg x_v \vee \neg x_{u_1} \vee \cdots \vee \neg x_{u_k}$.  (If vertex $v$ is isolated, its minimality constraint boils down to $\neg x_v$.)

If the graph has $n$ nodes and $e$ edges, the number of literals in the CNF formula is at most $n + 4e$.  It is "at most," because some minimality constraints are subsumed by others.  In the example above, the minimality constraints for $v_2$ and $v_4$ are subsumed by the constraints for $v_1$ and $v_5$, respectively.  Once subsumed constraints are removed, the CNF formula cannot be further simplified.
One then looks for a satisfying assignment that has the greatest number of asserted variables.

We now show that the decision version of the problem (does this graph have a minimal vertex cover of size at least $k$?) is NP-complete.  The proof is also going to work for size exactly equal to $k$.
The problem is in NP because a solution can be verified in polynomial time by checking that it has the required size and satisfies all constraints.  As noted in the comments, this does not require translation to SAT.
We show that the problem is NP-hard by reducing CNF SAT to it.  The strategy is adapted from M. D. Plummer, "Well-covered graphs: a survey", Quaestiones Mathematicae, 16(3):253–287, 1993.
Suppose we are given a propositional CNF formula $F$ that contains at least one clause, no empty clause, and no repeated clauses.  Furthermore, no clause contains both a variable and its negation, or repeated literals.  If any of these conditions are violated, either satisfiability is trivially decided (e.g., $F$ contains the empty clause) or $F$ can be easily simplified.
Let $F$ consists of $n$ clauses over $k$ variables.  We create a graph $G$ as follows.  There are $2k+n$ vertices: one vertex for each literal and one for each clause.  Each literal is connected to its negation.  Each clause is connected to all other clauses.  (The clause vertices form a clique of size $n$.)  Finally, every clause is connected to all its literals.  This construction can be completed in polynomial time.
It is readily seen that an independent set of $G$ may contain at most one clause vertex and at most $k$ literal vertices.  We can take this one step further: if $F$ is satisfiable, there are maximal independent sets of sizes $k$ and $k+1$, whereas if $F$ is unsatisfiable, all maximal independent sets have size $k+1$.
In fact, an assignment to the $k$ variables of $F$ identifies an independent subset of the literals of size $k$.  If the assignment satisfies all clauses, no clause vertex can be added to this independent set, which is therefore maximal; otherwise, one of the unsatisfied clauses can be added to the set.
Regardless of whether $F$ is satisfiable, we can build a maximal independent set of size $k+1$ as follows: we pick one clause and an independent set of $k$ literals that are not in the clause.  (That is, for every literal in the clause, we pick its negation, and for every variable not in the clause, we pick one of its literals.)
In sum, $F$ is satisfiable if and only if $G$ has maximal independent sets of size $k$.  Said otherwise, $F$ is satisfiable if and only if $G$ has minimal vertex covers of size at least $k+n$.


TITLE: Extension of a prime ideal in a Dedekind domain
QUESTION [0 upvotes]: Suppose that $A$ is a Dedekind domain and that $P$ is a prime ideal of $A$. Suppose that $K$ is the fraction field of $A$ and that $L$ is some finite separable extension of $K$. If $B$ is the integral closure of $A$ in $L$, is it necessarily the case that $PB\neq B$? If so, why?
I am not sure why this question has been closed. Apparently it has offended the hall monitors of MSE by contradicting some nebulous rule. However, I believe it is a straightforward question (and the comments indicate an answer exists in some book which I do not own and do not have access to!) and I hope the question will be reopened. Perhaps, after all, someone else has the same question!

REPLY [3 votes]: Yes, because of the Lying over property: as $B$ is integral over $A$ and the morphism  $A\longrightarrow B$ is injective, there exists a prime ideal $\mathfrak q\in\operatorname{Spec}B$ such that $\mathfrak q\cap A=\mathfrak p$, so $\mathfrak p B\subset \mathfrak q\varsubsetneq B$.


TITLE: Work done on system and surroundings in an irreversible adiabatic compression
QUESTION [0 upvotes]: In an adiabatic irreversible compression process, suppose the pressure $P_{ext}$ compresses the piston and does some work say 50J. (50J of energy is lost by surrounding).
Since the pressure $P_{int}$ is less than the $P_{ext}$, the work done by system on surrounding will be -20J(suppose). Negative sign shows that 20J of energy is lost my surrounding. But initially we saw that surrounding lost 50J! How to tackle this discrepancy? I am very confused.

REPLY [2 votes]: The force that the gas exerts on the inside face of the piston must be equal in magnitude and opposite in direction to the force the inside face of the piston exerts on the gas.  So the work the gas does on the piston must always be equal and magnitude and opposite in sign to the work the inside face of the piston (i.e., the surroundings) does on the gas.
The problem is that, for an irreversible compression or expansion, one cannot use the ideal gas law to calculate the force the gas exerts on the piston or the work done by the gas, because the ideal gas law is not valid for an irreversible compression or expansion.  The ideal gas law only applies at thermodynamic equilibrium, which is not present in an irreversible compression or expansion.  In the irreversible case, you will learn when you study fluid mechanics, that there are viscous stresses in the gas over and above that from the ideal gas behavior which affects the force per unit area at the piston face (as well as throughout the gas).
In the irreversible case,  if we want to calculate the work, our only option is to use the external force per unit area exerted by  the surroundings on the gas at the inside face of the piston (if this is known or specified).


TITLE: Real numbers x, y are randomly chosen from the interval [0, 1]. Are the probability that 3x + y ≤ 1 and the probability that 3x + y < 1 equal?
QUESTION [0 upvotes]: Real numbers x, y are randomly chosen from the interval [0, 1]. Is the probability that $3x + y ≤ 1$ equal to the probability that $3x+y<1$? (Because in the graph of the first case the inequality line is also considered, as it has $≤$ and we know considering a line doesn't add to the area. But in general sense, we're having points like $(x,y)=(0.2,0.4),(0.1,0.7)$ etc. adding to our probability whereas in the second case we don't.)

REPLY [1 votes]: You are dealing with continuous random variables. Events like $x=0.2,y=0.8$ have proabiblity $0$. A precise argument for $P(3x+y \leq 1)=P(3x+y <1)$ follows from the measure theoretic fact that $P(3x+y = 1)=0$ because the two dimensional Lebesgue measure of a stright line segement is $0$. [Intutively, the area of the line segment is $0$].


TITLE: Converse of the first fundamental homomorphism theorem
QUESTION [0 upvotes]: I have a question arising from the "Fundamental Homomorphism Theorem" as applied to groups (i.e. that the existence of a homomorphism $h: G\to H$ with kernel $J$ implies $H$ is isomorphic to the quotient group $G/J$).
As I understand it, Category Theory can be used to show that the rough converse is also true - i.e., that if a quotient group $G/J$ (where $J$ is a normal subgroup of $G$) is isomorphic to some group $H$, then there is a homomorphism $h: G\to H$ with kernel $J$.
Is this correct?
If so, is there a proof of the latter using only ideas from "standard" undergrad algebra?

REPLY [2 votes]: This is the easy direction: there is a natural map $q: G\rightarrow G/N$, given by $g\mapsto gN$. If $i: G/N\cong H$, then $q\circ i$ is a surjective homomorphism from $G$ onto $H$ with kernel $N$.