Isomorphic elliptic curves

To make things concrete, suppose that we're working in characteristic $ne 2,3$ (we can do something similar in those cases, though it gets messier), and the equation of the curve is

$E : y^2 = x^3 + a x + b$

and the equation of the twist is:

$E^{(d)} : d y^2 = x^3 + a x + b$.

Multiplying this by $d^3$:

$(d^2 y)^2 = (d x)^3 + a d^2 (d x) + d^3 b$

for this to be isomorphic to $E$ over $k$ it is necessary and sufficient that
there is a $lambda in k^*$ such that (see Silverman, or any other book on elliptic curves)
such that $a d^2 = a lambda^4$, $b d^3 = b lambda^6$. If $a,b ne 0$ then we must have
$lambda^6 = d^3$ and $lambda^4 = d^2$, which shows that $lambda^2 = d$ which you've ruled out. If $b=0$ you have, by taking square roots, $lambda^2 = pm d$, and only the minus sign is possible. If $a=0$ (and thus $b ne 0$) then $lambda^6 = d^3$. But then $(lambda^3/d)^2 = d^3/d^2 = d$, which you've also ruled out. Thus, only $b=0$ is possible, which is $j=1728$.

ac.commutative algebra - When does a quasicoherent sheaf vanish?

Let $F$ be a quasi-coherent sheaf on a scheme $X$. To check that $F$ vanishes it suffices to check that all the stalks of $F$ vanish. I would like to know whether it suffices to check that all the fibers of $F$ vanish.

(I think I am using standard terms: the tensor product over $O_X$ with the local ring at $x$ is the stalk, and the tensor product over $O_X$ with the residue field at $x$ is the fiber.)

It suffices to answer the question on an affine scheme. Let $R$ be a commutative ring. For each prime ideal $p$ of $R$ let $k(p)$ be the residue field of the local ring $R_p$. Let $M$ be an $R$-module, and suppose that $mathrm{Tor}_i(k(p),M) = 0$ for all $i$ and all $p$. (Tor taken in the category of $R$-modules). Does it follow that $M = 0$?

If $M$ is finitely generated, the answer is yes. In that case $M$ vanishes even when $mathrm{Tor}_0(k(p),M) = 0$ for all maximal $p$, by Nakayama's lemma. My question is whether there is a good replacement for Nakayama's lemma when $M$ is not finitely generated.

st.statistics - get standard error from correlation coefficient?

Look at the appropriate space in which your data would have a normal distribution, or look at the appropriate space in which your data set becomes linear.

This requires knowing the distribution of your experimental data as a prior value.

The correlation coefficient $R$ works best for linearly related data expressable as $y=mx+b$. While $R$ may have some informative value (positive or negative correlation) for non-linearly related variables, it really doesn't have a good clear meaning in non-linear cases.

Takes the logarithm of both sides and get

$$log(a)=b cdot log(T)$$

and see if you can calculate the correlation and do linear regression to find the best fit linear relation between $log(a)$ and $log(T)$. This way, you can see if the correlation coefficient can be informative for you.

But the key thing is in knowing the distribution (or expected distribution) of your data. If it is not normally distributed in the space which you're working in, try to find a transform which moves the data into a space where it has a linear normal Gaussian distribution.

math philosophy - How do they verify a verifier of formalized proofs?

I think the question you are asking - about how can we trust a formal proof - is a very important question. I have spent considerable effort developing software to specifically address this question. You touch on various things I have concentrated on.

It is true that various systems prominent in the formalisation of mathematics - including the HOL systems (HOL4, ProofPower HOL, HOL Light), Isabelle and Coq - are built according to the "LCF style", which means that all deduction must go via a relatively small kernel of trusted source code (implementing the primitive inference rules), and that this greatly reduces the risks of producing unsound proofs on these systems. It would also not be an exaggeration to say that almost everyone working in formal proof is happy with this situation. Indeed, probably most (but not those working on the above systems) feel that resorting to the LCF style is overkill and an unnecessary drain on user execution time and on development effort.

However, there are 3 major problems with this status quo:

A) Most "LCF-style" systems do not implement the LCF-style kernel idea as purely as may be expected. Some systems have back doors to creating "proved theorems", such as importing the statements (but not the proofs) of previously proved results from disk, and trust that the user will not abuse this. Also, to reduce execution time, most systems implement various derivable inference rules as primitives, multiplying up the size of the trusted source code. Also, the kernels of most systems typically incorporate large amounts of supporting code (e.g. for organising theories) and are not particularly clearly implemented, and so are difficult to review. It should be noted that HOL Light does not suffer from any of these problems.

B) The trusted aspects of an LCF-style system is NOT limited to the design/implementation of its LCF-style kernel. Like in all systems, it at least also includes the design of the concrete syntax and the implementation of the pretty printer, since, in practice, the user will only view results displayed in concrete syntax via the pretty printer. However, each system has problems with its concrete syntax and/or pretty printer that allows misleading information to be displayed to the user (e.g. by using irregular variables names, or names that are overloaded). I have found many ways of appearing to prove "false" in these systems! Also, depending on how the system is used, the parser is arguably also a trusted component.

C) The importance of the human process of checking that the intended result has in fact been proved (I call this "proof auditing") is generally greatly underestimated, and in practice often not even carried out at all. As you rightly point out, the axioms and definitions used in a formal proof need to be carefully checked, as well as the statement of the theorem itself. I have known subtle mistakes in definitions to render real formal proofs on real projects completely invalid.

I have developed an open source theorem prover called HOL Zero, that addresses issues A-C above and is designed for use in proof auditing and generally to be as trustworthy as possible. It has a watertight inference kernel, a well-designed concrete syntax and pretty printer, and the source code aims to be as clear and well-commented as possible. However, it should be noted that it does not have the advanced automatic and/or interactive proof facilities of the existing systems I mention above, and is not suited to developing large formal proofs. HOL Zero can be downloaded from here (it needs OCaml and a Unix-like operating system):

http://www.proof-technologies.com/holzero

The concept of checking one system using another is not only philosophically reassuring, but also of pressing need (due to the above issues A-C). As you say, what is needed is the ability to port proof objects between systems (the so called "de Bruijn criterion"). Strictly speaking, the de Bruijn criterion is as you state your requirement - the ability to capture a proof as an object (e.g. a text file) - rather than the LCF style (but let's not get too philosophical about the equivalence of these approaches). Anyway, there are some practical issues here:

1. The "dumb program" that you refer to needs to be surprisingly sophisticated, otherwise it loses much of its purpose. If it is just an LCF-style kernel, the data it outputs will be too slow to review for large projects. As you say, it needs to be human-friendly - a decent pretty printer is a practical necessity. Also, to make proof exporting (see next item) work in practice, it needs to work at least at a slightly higher level than the kernel, and so some supporting theory is required to be built. So yes, a dumb program is required, which should be as easy to understand as possible, but it is more challenging to build than a few lines of code.




2. Capturing proof objects in a suitably efficient way is a non-trivial exercise. The work that others mention above successfully port things like the base system of HOL Light, but are completely incapable of handling something the scale of Hale's HOL Light proof of the Jordan Curve Theorem, let alone Hale's Flyspeck Project (using HOL Light to check his non-formal proof of the Kepler Conjecture).




3. Some sort of neat and trivial correspondence of equivalent theory between systems is useful. This is better than importing language statements as huge expressions, in terms of some highly-complex embedding of one notation inside another, which would either greatly increase the complexity of the checking system or make its human usage difficult.

HOL Zero is primarily aimed at the "dumb program" proof checker role. The idea is it will import and replay proofs that have been exported from other HOL systems. I have implemented a proof exporting mechanism which, unlike others' mechanisms, handles with ease large proofs such as Hale's Jordan Curve proof and the (almost-complete) Flyspeck Project. I am currently working on a proof importing mechanism for HOL Zero. (Note that a former proof importing mechanism I developed worked on an old version of HOL Zero and successfully ported Hale's Jordan Curve proof and Harrison's proof of the consistency of the HOL Light kernel.)

ag.algebraic geometry - Equivalent Statements of Riemann Hypothesis in the Weil Conjectures

The reason why that inequality is equivalent to RH (for curves) is the functional equation.

I wrote out the details of the argument some years ago (in an unpublished book on zeta and $L$-functions), so it's easy to cut and paste it here. The polynomial $L(z)$ I speak about below would arise in practice as the numerator of the zeta-function of the curve, with $z = q^{-s}$ and the usual version of the Riemann hypothesis for $L(q^{-s})$ is equivalent to the statement that the reciprocal roots of $L(z)$ all have absolute value $sqrt{q}$. That's the form of the Riemann hypothesis I will be referring to in what follows.

Suppose we have a polynomial $L(z)$ over the complex numbers with constant term 1 and degree $d$, factored over its reciprocal roots:
$$
L(z) = (1 - alpha_1z)cdots(1-alpha_dz), alpha_j not= 0.
$$

Let $L*(z)$ be the polynomial with complex-conjugate coefficients to those of $L(z)$, so
$$
L*(z) = (1 - overline{alpha_1}z)cdots(1-overline{alpha_d}z).
$$
(Sorry, I want to make the asterisk into an exponent in this particular .tex situation, but it isn't working and I don't have time to figure it out.)
Assume $L(z)$ and $L*(z)$ are connected by the functional equation
$$
L(1/qz) = frac{W}{z^d}L*(z)
$$
for some constant $W$. If you compare coefficients of the same powers of $z$ on both sides, this functional equation implies the mapping $alpha mapsto q/alpha$ sends reciprocal roots of $L(z)$ to reciprocal roots of $L*(z)$ (and $W$ has absolute value $q^{d/2}$).

Lemma 1. Granting the functional equation above, the following conditions are equivalent:

i$)$ the reciprocal roots of $L(z)$ have absolute value $sqrt{q}$ (RH for $L(z)$),

ii$)$ the reciprocal roots of $L(z)$ have absolute value $leq sqrt{q}$.

Proof. We only need to show ii implies i.
Assuming ii, let $alpha$ be any reciprocal root of $L(z)$,
so $|alpha| leq sqrt{q}$. By the functional
equation, $q/alpha$ is a reciprocal
root of $L*(z)$, so $q/alpha = overline{beta}$
for some reciprocal root $beta$ of $L(z)$.
Then $|q/alpha| = |overline{beta}| = |beta| leq sqrt{q}$ and thus $sqrt{q} leq |alpha|$.
Therefore $|alpha| = sqrt{q}$ and i follows. QED

This lemma reduces the proof of the Riemann hypothesis for $L(z)$ from the equality $|alpha_j| = sqrt{q}$ for all $j$ to the upper bound $|alpha_j| leq sqrt{q}$ for all $j$. Of course the functional equation was crucial in explaining why the superficially weaker inequality implies the equality.

Next we want to show the upper bound on the $|alpha_j|$'s in part ii of Lemma 1 is equivalent to a $O$-estimate on sums of powers of the $alpha_j$'s which superficially seems weaker.

We will be interested in the sums
$$
alpha_1^n + cdots + alpha_d^n,
$$
which arise from the theory of zeta-functions as coefficients in an exponential generating function: since $L(z)$ has constant term 1, we can write (as formal power series over the complex numbers) $$L(z) = expleft(sum_{n geq 1}N_n z^n/nright)$$
and then logarithmic differentiation shows
$$
N_n = -(alpha_1^n + dots + alpha_d^n)
$$
for all $n geq 1$.

Lemma 2.
For nonzero complex numbers $alpha_1,dots,alpha_d$ and a
constant $B > 0$, the following are equivalent:

i$)$
For some $A > 0$, $|alpha_1^n + dots + alpha_d^n| leq AB^n$ for
all $n geq 1$.

ii$)$
For some $A > 0$ and positive integer $m$,
$|alpha_1^n + dots + alpha_d^n| leq AB^n$ for
all $n geq 1$ with $n equiv 0 bmod m$.

iii$)$ $|alpha_j| leq B$ for all $j$.

Part ii is saying you only need to show part i when $n$ runs through the (positive) multiples of any particular positive integer to know it is true for all positive integers $n$. It is a convenient technicality in the proof of the Riemann hypothesis for curves, but the heart of things is the connection between parts i and iii. (We'd be interested in part iii with $B = sqrt{q}$.) You could set $m = 1$ to make the proof below that ii implies iii into a proof that i implies iii. The passage from i to iii is what Dave is referring to in his answer when he cites the book by Iwaniec and Kowalski.

Proof.
Easily i implies ii and (since $|alpha_j| = |overline{alpha_j}|$)
iii implies i.
To show ii implies iii, we use a cute analytic trick. Assuming ii, the series
$$
sum_{n equiv 0 bmod m} (alpha_1^n + dots + alpha_d^n)z^n
$$
is absolutely convergent for $|z| < 1/B$, so the series defines a holomorphic function on this disc. (The sum is over positive multiples of $m$, of course.)
When $|z| < 1/|alpha_j|$ for
all $j$, the series can be computed to be
$$
sum_{j=1}^{d} frac{alpha_j^mz^m}{1-alpha_j^mz^m} =
sum_{j=1}^{d}frac{1}{1-alpha_j^mz^m} - d,
$$
so the rational function $sum_{j=1}^{d} 1/(1-alpha_j^mz^m)$ is holomorphic
on the disc $|z| < 1/B$. Therefore the poles of this rational function must have absolute value $geq 1/B$. Each $1/alpha_j$ is a pole, so $|alpha_j| leq B$ for all $j$. QED

Theorem.
The following are equivalent:

i$)$ $L(z)$ satisfies the Riemann hypothesis ($|alpha_j| = sqrt{q}$ for all $j$),

ii$)$ $N_n = O(q^{n/2})$ as $n rightarrow infty$,

iii$)$ for some $m geq 1$, $N_n = O(q^{n/2})$ as $n rightarrow
infty$ through the multiples of $m$.

Proof.
Easily i implies ii and ii implies iii.
Assuming iii, we get $|alpha_j| leq sqrt{q}$ for all $j$ by
Lemma 2, and this inequality over all $j$ is equivalent to i
by Lemma 1. QED

Brandon asked, after Rebecca's answer, if the inequality implies the Weil conjectures (for curves) and Dave also referred in his answer to the Weil conjectures following from the inequality. In this context at least, you should not say "Weil conjectures" when you mean "Riemann hypothesis" since we used the functional equation in the argument and that is itself part of the Weil conjectures. The inequality does not imply the Weil conjectures, but only the Riemann hypothesis (after the functional equation is established).

That the inequality is logically equivalent to RH, and not just a consequence of it, has some mathematical interest since this is one of the routes to a proof of the Weil conjectures for curves.

P.S. Brandon, if you have other questions about the Weil conjectures for curves, ask your thesis advisor if you could look at his senior thesis. You'll find the above arguments in there, along with applications to coding theory. :)

gt.geometric topology - Homotopies of triangulations

The standard name for this type of relation between two structures on $X$ is concordance rather than homotopy. If two structures on $X$ are isotopic (with the respect to the appropriate homeomorphism group), then they are concordant, but not necessarily vice versa. In some cases you can also assign a separate meaning to homotopy, but I don't think that it means the same thing as concordance.

There are then two levels to your question. A triangulation $T$ of $X$ induces a piecewise linear structure $mathcal{P}$. You could ask whether the PL structures $mathcal{P}$ and $mathcal{P}'$ are isotopic or concordant, without worrying about the original triangulations. For simplicity suppose that $X$ is a closed manifold. Then at least in dimension $n ge 5$, Kirby-Siebenmann theory says that the set of PL structures on $X$ up to isotopy are an affine space (or torsor) of $H^3(X,mathbb{Z}/2)$. I think that the concordance answer is the same, because the Kirby-Siebenmann invariant comes from the stable germ-theoretic tangent bundle of $X$. In other words, two PL structures give you two different sections of a bundle on $X$ whose fiber is $text{TOP}(n)/text{PL}(n)$, the group of germs of homeomorphisms of $mathbb{R}^n$ divided by the subgroup of germs of PL homeomorphisms. Stabilization in this case means replacing $n$ by $infty$ by adding extra factors of $mathbb{R}$. If $n = 4$, then up to isotopy there are lots of PL structures on many 4-manifolds, as established by gauge theory. But I think that the concordance answer is once again Kirby-Siebenmann. (I learned about this stuff in a seminar given by Rob Kirby — I hope that I remembered it correctly! You can also try the reference by Kirby and Siebenmann, although it is not very easy to read.)

There is a coarser answer than the one that I just gave. I tacitly assumed that the triangulations not only give you a PL structure (which always happens), but that they specifically give you a PL manifold structure, with the restriction that the link of every vertex is a PL sphere. These are called "combinatorial triangulations". It is a theorem of Edwards and Cannon that $S^5$ and other manifolds also have non-combinatorial triangulations. If your question is about these, then it is known that they are described by some quotient of Kirby-Siebenmann theory, but it is not known how much you should quotient. It is possible that every manifold of dimension $n ge 5$ has a non-combinatorial triangulation, and that PL structures are always concordant in this weaker sense. It is known that you should quotient more than trivially, that there are manifolds that have a non-combinatorial triangulation but no PL structure. (I think.)

The other half of the question is to give $X$ a distinguished PL structure $mathcal{P}$, and to look at triangulations $T$ and $T'$ that are both PL with respect to $mathcal{P}$. In this case there are two good sets of moves to convert $T$ to $T'$. First, you can use stellar moves and their inverses. A stellar move consists of adding a vertex $v$ to the interior of a simplex $Delta$ (of some dimension) and supporting structure to turn the star of $Delta$ into the star of $v$. The theorem that these moves suffice is called the stellar subdivision theorem. (The theorem is due to Alexander and Newman and it is explained pretty well in the book by Rourke and Sanderson.) The other set of moves are specific to manifolds and they are the bistellar moves or Pachner moves. One definition is that a bistellar move is a stellar move that adds a vertex $v$ plus a different inverse stellar move that removes $v$ (hence the name). But a clearer definition is that in dimension $n$, a bistellar move replaces $k$ simplices by $n-k+1$ simplices in the minimal way, given by a local $n+1$ concordance that consists of attaching a single $n+1$-dimensional simplex. The theorem that these moves work is due to Pachner. Pachner's moves in particular give you a shellable triangulation of $X times [0,1]$.

Even though the bistellar moves are motivated by concordance and the stellar moves are not, it is not hard to make concordance triangulations for stellar moves as well.

soft question - How many different representations of pi can we come up with?

Let me explain: a friend of a friend is opening a new pizza restaurant called "Pi", and he's looking to decorate his walls with pi-related material: formulas, equations, theorems w/ proof, diagrams, etc. Any suggestion is welcome, so long as it meets these two criteria:

1. It has to be mathematically correct.


2. It has to be either a representation of pi itself or lead directly to a representation of pi.

So for example, this is okay: $sum_{n=1}^{infty} frac{1}{n^2}$ (because it equals $frac{pi^2}{6}$)
But this is not: $frac{22}{7}$.

How many can we come up with?

fa.functional analysis - Advantages of a back-propagation neural network over other function approximation methods

Hello.

Let's say I have a set of input vectors $I = {mathbf{x_1}, dots, mathbf{x_k}} subset mathcal{R}^m$ and a set of output vectors $O = {mathbf{y_1}, dots, mathbf{y_k}} subset mathcal{R}^n$, and I want to obtain a mapping $f : mathcal{R}^m to mathcal{R}^n$ such that

$$ f(mathbf{x_i}) = mathbf{y_i} + epsilon_i, forall i in {1, dots, k}$$

where $epsilon_i$ is small, and this mapping should be continuous at least around the input/output pairs.

There are many ways of doing so.

If we suppose that the input/output pairs won't change, what are the advantages of using an Artificial Neural Network over other methods to approximate functions?

EDIT: when I say advantages, I mean the practical advantages on the use of neural networks over other function approximation methods on any domain that use the neural networks.

For example, if we think of (the canonical example of) handwriting recognition that mailing services might use to read zip codes, the neural network is nothing more than a function that maps, let's say, [0, 1]^35 (if we think of a 5x7 grid, in which the values are the "intensity" or "amount" of the ink on each cell) to [0, 1]^10 (corresponding to each digit between 0 and 9, the value being the probability of the digit). So, in this case, if we think that we will write a software to do this recognition, and that the patterns will never change, we could simply have used another technique to map the input to the output. If we use any method that produces a continuous mapping, small "variations" on the handwritting wouldn't affect too much the output of the function.

Thanks.

pr.probability - The density of x_1^n+x_2^n where x_i are Gaussian

Firstly you forgot to multiply the
density $f(x^n=y)$ by $1/sqrt{2pi}$. I think if you
obtained the density of the random variable $X_{1,2}=X_1^n+X_2^n$ by
the convolution method, the problem no more posed , because for
$X_1^n+X_2^n+X_3^n=X^n_{1,2}+X_3^n=X^n_{1,2,3}$, and you have the
density of $X^n_{1,2}$, the density of $X^n_{3}$, you can calculate
there convolution, i.e the density of $X^n_{1,2,3}$. If the calculation is
very difficult with the convolution (I think) you can
use the characteristic function. You calculate the function
characteristic of the variable $X_1^n$ that one noted
$psi_{X_1^n}(t)$. As the two variables $X_1^n$ and $X_2^n$ are
i.i.d, then $psi_{X_1^n+X_2^n}(t)=psi_{X_1^n}(t)cdot
psi_{X_2^n}(t)=(psi_{X_1^n}(t))^2$ and so on for
variable $X_1^n+X_2^n+...+X_k^n$ we will have
$psi_{X_1^n+X_2^n+ldots +X_k^n}(t)=(psi_{X_1^n}(t))^k$. Just well calculate $psi_{X_1^n}(t)$.

gr.group theory - Affine Weyl groups as Coxeter groups

In the abstract Bourbaki set-up, the affine Weyl group is defined to be a
semidirect product of an irreducible Weyl group with its coroot lattice.
This is naturally a Coxeter group, characterized in terms of its
positive semidefinite Coxeter matrix. The basic theory is developed
independently of applications in Lie theory, but is directly usable if you
start with a connected semisimple algebraic group (over an algebraically
closed field) and require its root system to be irreducible of type A, B,
etc. Most of the time this causes no trouble. While it is natural to work
with a connected reductive group, people often use the expression "affine
Weyl group" too loosely in this general context. For example, the standard
features of alcove geometry require irreducibility. Otherwise you have
to deal with products of simplexes, etc. In any case, the difference between
reductive and semisimple groups such as general linear and special linear
is sometimes significant.

In the Iwahori-Matsumoto (or Bruhat-Tits) setting over local fields, a
more intrinsic affine Weyl group occurs directly within the structure of
the group itself. Here one has to be cautious about applying
abstract Coxeter group theory or BN-pair theory, as I believe most authors
are. Already in the proceedings of the 1965 Boulder AMS summer institute,
Iwahori had to formulate a more complicated "generalized BN-pair" formalism
for this situation. I'm not sure what has become standard by now in the
literature.

In other situations (the classical study of compact Lie groups, or
the later application of affine Weyl groups in modular representation
theory starting with Verma) there is usually no difficulty about specializing
to the irreducible case. Here the affine Weyl group lives outside the
actual group under study. This is the situation I'm most comfortable with.

You need to make precise the setting in which you really want to study reductive groups, in order to adapt the Bourbaki language and results.
There are several distinct issues here: 1) Extra care is needed in treating
disconnected algebraic groups such as orthogonal groups, or in treating
reductive rather than semisimple groups. 2) Adjoint groups, simply
connected groups, and the occasional intermediate type: not all details of
structure are exactly the same. 3) Most important for working over
local fields is the natural use of an "extended affine Weyl group" (as in
much of Lusztig's work involving Hecke algebras, cells, etc.). Here you
start with the Bourbaki version of the affine Weyl group (a Coxeter group)
and form a semidirect product with a finite group $Omega$ isomorphic to the weight lattice mod root lattice (universal center). This amounts to
working with a semidirect product of the Weyl group and the full (co)weight
lattice rather than the (co)root lattice. Fortunately it's easy to extend
notions like length function to this extended group.

EDIT: Besides Bourbaki's treatment of Coxeter groups and root systems (1968),
foundational papers from that era include Iwahori-Matsumoto (IHES Publ. Math. 25, 1965), at http://www.numdam.org, and Iwahori's 1965 article in the AMS Boulder proceedings
http://www.ams.org/books/pspum/009/0215858/pspum0215858.pdf, followed by much more technical work by Bruhat-Tits.
Lusztig has written many technical papers on extended affine Weyl groups and corresponding affine Hecke algebras, including his four part series on cells in affine Weyl groups and later work on multiparameter cases. Much of this work is motivated by reductive groups over local fields, as well as the modular representation theory of reductive groups and their Lie algebras (where "linkage" of weights appears at first relative to an extended affine Weyl group).

ac.commutative algebra - Weakened conditions for étale + X implies faithfully flat.

Let $F:R to S$ be an étale morphism of rings. It follows with some work that $f$ is flat.

However, faithful flatness is another story. It's not hard to show that faithful + flat is weaker than being faithfully flat. An equivalent condition to being faithfully flat is being surjective on spectra.

The question:
Is there any further condition we can require on an étale morphism that implies faithful flatness?

"Faithfully flat implies faithfully flat" or "surjective on spectra is equivalent to faithfully flat" do not count. The answer should in some way use the fact that the morphism is étale (or at least flat).

As you can see by the tag, all rings commutative, unital, etc.

Edit: Why faithfully flat is weaker than faithful + flat.

Edit 2: I resent the voting down of this question without accompanying comments as well as the voting up of the glib and unhelpful answer below. It's clear that some of you are in the habit of voting on posts based on the poster rather than the content, and I think that is shameful. There is nothing I can do because none of you has the basic decency to at least leave a comment. I am completely at your mercy. You've won. I hope it's made you very happy.

Edit 3: To answer Emerton's comment, I asked here after:

a.) Reading this post by Jim Borger

b.) Asking my commutative algebra professor in an e-mail

Which led me to believe (perhaps due to a flawed reading of said sources) that this was a harder question than it turned out to be.

ag.algebraic geometry - Why is this not an algebraic space?

This question is related to the following question which I've just seen which was posted by Anton. His question is whether a algebraic space which is a group object is necessarily a group scheme, and the answer appears to be YES. Now my naive idea of what an algebraic space is is that it is the quotient of a scheme by an etale equivalence relation, but I seem to be confusing myself. I'm hoping someone will help lead me out of my confusion.

Let me first consider an analogous topological situation, where the answer is no. We can consider the category of smooth spaces, by which I mean the category of sheaves on the site of smooth manifolds which are quotients of manifolds by smooth equivalence relations (with discrete fibers).

Here is an example: If we have a discrete group G acting (smoothly) on a space X, we can form the equivalence relation $R subset X times X$, where R consists of all pairs of points $(x,y) in X times X$ where $y= gx$ for some $g in G$. If R is a manifold, then the sheaf $[X/R]$ (which is defined as a coequalizer of sheaves) is a smooth space.

Here is an example of a group object in smooth spaces: We start with the commutative Lie group $S^1 = U(1)$. Now pick an irrational number $r in mathbb{R}$ which we think of as the point $w = e^{2 pi i r}$. We let $mathbb{Z}$ act on $S^1$ by "rotation by r" i.e.

$mathbb{Z} times S^1 to S^1$

$ (n, z) mapsto w^n z$

This gives us an equivalence relation $R = mathbb{Z} times S^1 rightrightarrows S^1$, where one map is the action and the other projection. The fibers are discrete and the quotient sheaf is thus a smooth space, which is not a manifold. However the groupoid $R rightrightarrows S^1$ has extra structure. It is a group object in groupoids, and this gives the quotient sheaf a group structure.

The group structure on the objects $S^1$ and morphisms $R$ are just given by the obvious group structures. Incidentally, this group object in groupoids serves as a sort of model for the "quantum torus", 0604.5405.

Now what happens when we try to copy this example in the setting of algebraic spaces and schemes?

Let's make it easy and work over the complex numbers. An analog of $S^1$ is the group scheme
$mathbb{G}_m / mathbb{C} = spec mathbb{C}[t,t^{-1}]$.

Any discrete group gives rise to a group scheme over $spec mathbb{C}$ by viewing the set $G$ as the scheme

$sqcup_G spec mathbb{C}$

So for example we can view the integers $mathbb{Z}$ as a group scheme. This (commutative) group scheme should have the property that a homomorphism from it to any other group scheme is the same as specifying a single $spec mathbb{C}$-point of the target (commutative) group scheme.

A $spec mathbb{C}$ point of $spec mathbb{C}[t,t^{-1}]$ is specified by an invertible element of $mathbb{C}$. Let's fix one, namely the one given by the element $w in S^1 subset mathbb{C}^times$. So this gives rise to a homomorphism $mathbb{Z} to mathbb{G}_m$ and hence to an action of $mathbb{Z}$ on $mathbb{G}_m$.

Naively, the same construction seems to work to produce a group object in algebraic spaces which is not a scheme. So my question is: where does this break down?

There are a few possibilities I thought of, but haven't been able to check:

1. Does $R = mathbb{Z} times mathbb{G}_m$ fail to be an equivalence relation for some technical reason?


2. Do the maps $R rightrightarrows mathbb{G}_m$ fail to be etale?


3. Is there something else that I am missing?

computer science - Closed form of a nonlinear recurrence sequence.

As has already been explained, there is no hope in general of finding explicit solutions to nonlinear recurrences. However, for your example, it is possible to find $lim_{ntoinfty}f_n(X)$ for all real $X$.

The function $g(x)=(x^2+x)/2$ has two fixed points: $x=0$ (atractor) and $x=1$ (repulsor). Its respective stable sets are $(-2,1)$ and ${-2,1}$; $(-infty,-2)cup(1,+infty)$ is the stable set of $+infty$. Thus,

$$lim_{ntoinfty}f_n(X)=left{matrix{0, & Xin(-2,1)cr 1, & Xin{-2,1}cr +infty, & Xin(-infty,-2)cup(1,+infty)}right.$$

at.algebraic topology - the hopf invariant of the hopf construction

This is my attempt at an answer. I think I might be off in justifying the second diagram. It's based on the proof in Bredon, but I think it might be a little simpler. Corrections are welcome, of course!

---

For convenience, we introduce some notation and conventions. We define subsets of $$S^n= { (c,t):cin S^{n-1},tin I } /sim$$ by $X={(c,t):tleq 1/2}$, $Y={(c,t):tgeq 1/2}$, and $Z={(c,1/2)}$. We define subsets of $$S^{2n-1}={ (a,t,b):a,bin S^{n-1},tin I}$$ by $A={(a,t,b)in S^{2n-1}:tleq 1/2}$ and $B={(a,t,b)in S^{2n-1}:tgeq 1/2}$. We define subsets of $Acap B={(a,1/2,b)}$ by $S^{n-1}_A = {(a,1/2,b_0)}$ and $S^{n-1}_B = {(a_0,1/2,b)}$ for fixed $a_0,b_0in S^{n-1}$. We consider $S^{2n-1}$ as the boundary of $e^{2n}$; in this cell, $S^{n-1}_A$ is the boundary of a cell $e^n_A$ and $S^{n-1}_B$ is the boundary of a cell $e^n_B$. We write $K=S^ncup_{h(g)}e^{2n}$ for the complex in which we must compute $H(h(g))$. Throughout, all cohomology is integral.

To compute cup products in $K$, we use the commutative diagram

H^n(K) x H^n(K) ---------> H^{2n}(K)
       ^             cup       ^
       |                       |
       |             cup       |
H^n(K,X) x H^n(K,Y) -----> H^{2n}(K,S^n)

which follows from the map $(K,emptyset,emptyset)rightarrow (K,X,Y)$ and naturality; the vertical maps are isomorphisms by the long exact sequence in cohomology for pairs. Let the generator $x$ of $H^n(K)$ correspond to the generator $x_Y$ of $H^n(K,X)$ and the generator $x_X$ of $H^n(K,Y)$, so that $x_Ycup x_X$ in $H^{2n}(K,S^n)$ corresponds to $x^2$ in $H^{2n}(K)$.

To understand the image of the cup product, we use the evident map $j:(e^{2n},A,B)rightarrow (K,X,Y)$. We have the diagram

H^n(K,X)  =  H^n(S^n,X)  =  H^n(Y,Z)  =  H^{n-1}(Z)
   |                                       |
   | j^*                                   | j^*
   |                                       |
   V                                       V
H^n(e^{2n},A) = H^n(e^n_A,S^{n-1}_A) = H^{n-1}(S^{n-1}_A)

which commutes because of the naturality of the isomorphisms involved (namely, along the top: cellular cohomology, excision and homotopy invariance, lexseq for pairs; along the bottom: homotopy invariance, lexseq for pairs). By definition of degree, the map $j^ast:H^{n-1}(Z)rightarrow H^{n-1}(S^{n-1}_A)$ is multiplication by $alpha$. Hence, so is the map $j^ast : H^n(K,X)rightarrow H^n(e^{2n},A)$. Similarly, the map $j^ast:H^n(K,Y)rightarrow H^n(e^{2n},B)$ is multiplication by $beta$. Now, $j^ast:H^{2n}(K,S^n)rightarrow H^{2n}(e^{2n},S^{2n-1})$ is an isomorphism, and $j^ast(x_Ycup x_X)$ is $alphabeta$ times a generator of $H^{2n}(e^{2n},S^{2n-1})$. Thus $x_Ycup x_X$ is $alphabeta$ times a generator of $H^{2n}(K,S^n)$. So by the first diagram, $H(h(g))=alphabeta$.

gn.general topology - What are the topological properties of the metric space retained (inherited) for its completion

I was going to suggest that all the connectivity properties were either preserved or sometimes acquired by completion: e.g. a totally disconnected $X$ may become a path-connected $bar X$, and the same is true for the other locally-defined connectivity properties I considered on that list.

But this is not true in the case of simple connectivity, or n-connectivity, because these properties depend on each point. As far as I can tell you can change them any way you like. You could put a metric on a CW-complex, but for $bar X$ any CW complex of countably many cells, you can remove a point to change the homotopy type of $X$ as compared to $bar X$, or just as above, let $X$ be a discrete dense set.

Or make $X$ two horizontal line segments one over the other, connected by line segments depicting an ordered bijection between dense subsets, or higher-dimensional analogues, so that $bar X$ is a cube.

Or let $X$ be the cone of any topological space with an appropriate metric, but with the point at the tip removed, so whatever the homotopy type of $X$, $bar X$ is contractible. I think you could even selectively remove points from a CW complex to redesign homotopy groups in more interesting ways.

pr.probability - Correlation in graph coloring

Question 1. Yes, efficient algorithm for Cor exists for graphs of low tree-width

Cast this in the framework of probabilistic graphical models and then use the junction tree algorithm, which scales exponentially in tree-width of the graph.

In particular, let $G$ be a graph over $n$ vertices with edges $E$. Let $x in [1,2,ldots, k]^n$. Define probability distribution over $x$ as follows

$$p(x)=exp{(sum_{(ij)in E} mathbf{I}(x_ine x_j))}/Z$$

Where $Z$ is a constant chosen to make this a valid probability distribution.
Then
$$text{Cor}(G,k,u,v)=sum_{c=1}^k p(x_u=c,x_v=c)$$

Computing p in the formula above in graphs that are not trees is not trivial, but can be done efficiently if the tree-width is low, look at page 370 of Koller's "Probabilistic Graphical Models" for details on that particular form of query.

Question 2. Yes, for graphs with low degree or large number of colors. For instance, here the authors conjecture that colorings on graphs with degree at most k and at least k+1 number of colors exhibits "strong spatial mixing", which would imply that the algorithm they give to approximate the marginals could also give a guaranteed approximation to your problem in polynomial time

ag.algebraic geometry - Definition of étale for rings

You say that a ring homomorphism $phi: A to B$ is étale (resp. smooth, unramified), or that $B$ is étale (resp. smooth, unramified) over $A$ is the following two conditions are satisfied:

• $A to B$ is formally étale (resp. formally smooth, formally unramified): for every square-zero extension of $A$-algebras $R' to R$ (meaning that the kernel $I$ satisfies $I^2 = 0$) the natural map $$mathrm{Hom}_A(B, R') to mathrm{Hom}_{A}(B, R)$$ is bijective (resp. surjective, injective).


• $B$ is esentially of finite presentation over $A$: $A to B$ factors as $A to C to B$, where $A to C$ is of finite presentation and $C to B$ is $C$-isomorphic to a localization morphism $C to S^{-1}C$ for some multiplicatively closed subset $S subset C$.

The second condition is just a finiteness condition; the meat of the concept is in the first one. Formal smoothness is often referred to as the infinitesimal lifting property. Geometrically speaking, it says that if the affine scheme $mathrm{Spec}B$ is smooth over $mathrm{Spec}A$, then any map from $mathrm{Spec}B$ to $mathrm{Spec}R$ lifts to any square-zero (and hence any infinitesimal) deformation $mathrm{Spec}R'$. Moreover, if $mathrm{Spec}B$ is étale over $mathrm{Spec}A$ this lifting is unique.

Differential-geometrically, unramifiedness, smoothness and étaleness correspond to the tangent map of $mathrm{Spec}phi$ being injective, surjective and bijective, respectively. In particular, étale is the generalization to the algebraic case of the concept of local isomorphism.

There are two references you might want to consult. The first one, in which you can read all about the formal properties of these morphisms, is Iversen's "Generic Local Structure in Commutative Algebra". The second one, Hartshorne's "Deformation Theory", will give you a lot of information about the geometry; section 4 of chapter 1 (available online) talks about the infinitesimal lifting property.

EDIT: The EGA definition of étale morphism of rings is slightly different from the above, in the sense that it requires finite presentation, not just locally of finite presentation: see the comments below.

gr.group theory - Groupoid structure on G/H?

One answer to your question is that there is always the notion of an "action groupoid", although this does not reproduce the group structure on $G/H$ when $H$ is normal.

Let $G$ be a group acting on a set $X$. (There are generalizations when both $X,G$ are groupoids.) Then the action groupoid $X//G$ is the groupoid with objects $X$, and morphisms $Xtimes G$. More precisely, if $x,y in X$, then $hom(x,y) = { gin G text{ s.t. } gx = y}$. The groupoid axioms are essentially obvious.

For example, let $X = G/H$ be the set of left $H$-cosets. Then the action groupoid is very simple: it is connected (any object is isomorphic to any other), with $text{aut}(e) = H$, where $e = eH$ is the trivial left $H$-coset. And $hom(e,g) = gH$, where $g = gH$ is a coset.
So as a discrete groupoid, this action groupoid is equivalent to ${text{pt}}//H$, also sometimes called the "classifying groupoid" $mathcal B H$, because the geometric realization of the nerve of this groupoid is the usual classifying space of $H$.

In short-hand, we have the following equation:
$$ (G/H) //G cong 1//H$$
where $cong$ denotes equivalence of groupoids. (Actually, since I'm talking about left actions, I should probably write $G backslash backslash X$ for the action groupoid, and so the equation really should be $G backslash backslash (G/H) = H backslash backslash 1$, but typing "/" is much faster than typing "backslash", so I won't use the better notation.)

But you are probably asking a different question. Recall that when $H$ is normal, then $G/H$ has a group structure, which is to say there is a groupoid with one object and whose morphisms are elements of $G/H$. Of course, as you know, if $H$ is not normal, then $G/H$ does not have a natural group structure, because in general $g_1Hg_2H$ is not a left $H$-coset.

You can try to do the following. Any set is naturally a groupoid with only trivial morphisms, and then the set $G/H$ is equivalent to the groupoid $G//H$, where $H$ acts on the set $G$ by translation = right multiplication. (This is because $H$ acts on $G$ freely.) But $G$ is actually more than a set: it is a group. So let's think about it as a "groupal groupoid" or "2-group", i.e. a 2-groupoid with only one object; in this case, it will also only have identity 2-morphisms.

Then I guess you should try to form the "action 2-group" or something, by adding 2-morphisms for the translations by $H$. But I think that if you do, you no longer have a groupal groupoid: I think that if $H$ is not normal, then the group multiplication is not a functor from the action groupoid $G//H$.

The other only thing I can think of is to define $K = text{Norm}_GH$, the normalizer, and then $K/H$ is a group that embeds in $G/H$, so let the objects of your groupoid be cosets of $K$ and the morphisms given by $K/H$?

So, long story short: in the way that I think you are hoping, no, $G/H$ is not naturally a groupoid.

big picture - Heuristic behind the Fourier-Mukai transform

First, recall the classical Fourier transform. It's something like this: Take a function $f(x)$, and then the Fourier transform is the function $g(y) := int f(x)e^{2pi i xy} dx$. I really know almost nothing about the classical Fourier transform, but one of the main points is that the Fourier transform is supposed to be an invertible operation.

The Fourier-Mukai transform in algebraic geometry gets its name because it at least superficially resembles the classical Fourier transform. (And of course because it was studied by Mukai.) Let me give a rough picture of the Fourier-Mukai transform and how it resembles the classical situation.

1. Take two varieties $X$ and $Y$, and a sheaf $mathcal{P}$ on $X times Y$. The sheaf $mathcal{P}$ is sometimes called the "integral kernel". Take a sheaf $mathcal{F}$ on $X$. Think of $mathcal{F}$ as being analogous to the function $f(x)$ in the classical situation. Think of $mathcal{P}$ as being analogous to, in the classical situation, some function of $x$ and $y$.




2. Now pull the sheaf back along the projection $p_1 : X times Y to X$. Think of the pullback $p_1^ast mathcal{F}$ as being analogous to the function $F(x,y) := f(x)$. Think of $mathcal{P}$ as being analogous to the function $e^{2pi i xy}$ (but maybe not exactly, see below).




3. Next, take the tensor product $p_1^ast mathcal{F} otimes mathcal{P}$. This is analogous to the function $F(x,y) e^{2pi i xy}$ $=$ $f(x)e^{2pi i xy}$.




4. Finally, push $p_1^astmathcal{F} otimes mathcal{P}$ down along the projection $p_2: X times Y to Y$. The result is the Fourier-Mukai transform of $mathcal{F}$ --- it is $p_{2,ast} (p_1^ast mathcal{F} otimes mathcal{P})$. This last pushforward step can be thought of as "integration along the fiber" --- here the fiber direction is the $X$ direction. So the analogous thing in the classical situation is $g(y) = int f(x)e^{2pi i xy}dx$ --- the Fourier transform of $f(x)$!

But to make all of this actually work out, we have to actually use the derived pushforward, not just the pushforward. And so we have to work with the derived categories.

When $X$ is an abelian variety, $Y$ is the dual abelian variety, and $mathcal{P}$ is the so-called Poincare line bundle on $X times Y$, then the Fourier-Mukai transform gives an equivalence of the derived category of coherent sheaves on $X$ with the derived category of coherent sheaves on $Y$. I think this was proven by Mukai. I think this is supposed to be analogous to the statement I made about the classical Fourier transform being invertible. In other words I think the Poincare line bundle is really supposed to be analogous to the function $e^{2pi i xy}$. A more general choice of $mathcal{P}$ corresponds to, in the classical situation, so-called integral transforms, which have been previously discussed here. This is probably why $mathcal{P}$ is called the integral kernel. You may also be interested in reading about Pontryagin duality, which is a version of the Fourier transform for locally compact abelian topological groups --- this is obviously quite similar, at least superficially, to Mukai's result about abelian varieties. However I don't know enough to say anything more than that.

There are some cool theorems of Orlov, I forget the precise statements (but you can probably easily find them in any of the books suggested so far), which say that in certain cases any derived equivalence is induced by a Fourier-Mukai transform. Note that the converse is not true: some random Fourier-Mukai transform (i.e. some random choice of the sheaf $mathcal{P}$) is probably not a derived equivalence.

I think Huybrechts' book "Fourier-Mukai transforms in algebraic geometry" is a good book to look at.

Edit: I hope this gives you a better idea of what is going on, though I have to admit that I don't know of any good heuristic idea behind, e.g., Mukai's result --- it is analogous to the Fourier transform and to Pontryagin duality, and thus I suppose we can apply whatever heuristic ideas we have about the Fourier transform to the Fourier-Mukai transform --- but I don't know of any heuristic ideas that explain the Fourier-Mukai transform in a direct way, without appealing to any analogies to things that are outside of algebraic geometry proper. Hopefully somebody else can say something about that.

But --- there is certainly something deep going on. Just as CommRing behaves a lot like Set^op, I think there is probably some kind of general phenomenon that sheaves (or vector bundles) behave a lot like functions, which is what's happening here. Pullback of sheaves behave a lot like pullback of functions... Pushforward of sheaves behave a lot like integration of functions... Tensor product of sheaves behave a lot like multiplication of functions...

dg.differential geometry - Is every group object in TopMan a Lie group?

I just wanted to add that there is a fairly easy proof for your final question: Is every continuous homomorphism between Lie groups actually smooth?

The theorem we need is the closed subgroup theorem (also called the Cartan Theorem): If H is a topologically closed subgroup of a Lie group G, then H is actually an embedded Lie subgroup.

Granting this, one proves all continuous homomorphisms are smooth as follows:

Given Lie groups H and G with $f:Hrightarrow G$ a continuous homomorphism, consider the subgroup $K$ of $Htimes G$ given by the graph of $f$. The graph is a closed subset of $Htimes G$ precisely because $f$ is continuous, and hence, by the closed subgroup theorem, the graph is an embedded smooth submanifold of $Htimes G$. Thus, the restriction of the two canonical projection maps $pi_1:Htimes Grightarrow H$ and $pi_2:Htimes Grightarrow G$ are smooth when restricted to K.

Now, $pi_1$ restricted to $K$ is clearly* a diffeomorphism onto $H$, and hence has a smooth inverse and so is smooth. But then we find that $f = pi_2circ pi_1^{-1}$ is a composition of smooth maps, and hence is smooth. (To be clearer, the $pi_1^{-1}$ means the inverse of $pi_1:Krightarrow H$.)

*- (Edited in due to comments). One knows by Sard's theorem that there is a point $pin K$ such that $d_p pi_1$ is invertible (of full rank). I claim that this implies that for all $qin K$, $d_q pi_1$ is invertible. The point is that $pi_1$ is group homomorphism, which is the same as saying $pi_1circ L_{qp^{-1}} = L_{pi_1(qp^{-1})}circ pi_1$, where $L_g$ denotes left multiplication by $g: L_g(h) = gh$. Taking the differentials at p on each side of this equation and using the chain rule, one finds

$$d_q pi_1 circ d_p L_{qp^{-1}} = d_{pi_1(p)}L_{pi_1(qp^{-1})}circ d_p pi_1.$$

The fact that $L_g$ is a diffeomorphism (with inverse $L_{g^{-1}}$) implies that $dL$ is invertible at any point, and hence we see that

$$d_qpi_1 = d_{pi_1(p)}L_{pi_1{qp^{-1}}}circ d_p pi_1circ d_pL_{pq^{-1}};$$ i.e., that $d_q pi_1$ is a composition of invertible maps, and hence is itself invertible.

puzzle - How to attack this diophantine equation in 3 variables?

Note that x^3 - x = (x-1)x(x+1). Now let x = (a+b+c)
and rewrite the equation as
(x-1)x(x+1) = 987654320*a + 123456788*b.
Let D be gcd(987654320,123456788) = 16. There are
integers A, B so that 987654320*A + 123456788*B = D,
e.g (1, -8). Pick your favorite x so that x^3 - x is a
multiple of D, say kD, let a = kA and b = kB, and then
set c to (x - (a+b)). If you need a and b to be
positive, choose x large enough so that kD is big
enough so that you can subtract multiples of
987654320*123456788/D^2 from, say ka and add them to kb.
If you need c to be positive as well, then pick x not
too large, as RHS < 10^9 * (a+b) < 10^9 x, so x larger
than 10^5 will not get you positive values of c.

Gerhard "Ask Me About System Design" Paseman, 2010.01.12

mg.metric geometry - How to compute the average distance till intersection within a triangle in R^2?

We can start by solving the problem for an arbitrary triangle and a fixed direction, say the upward direction, as we can always rotate the whole figure into that position.

In the generic case, no edge of the triangle is horizontal. Thus the triangle has a "top" vertex at (0, 0) -- this is the vertex with the largest y-coordinate. Without loss of generality, rescale so that the edge opposite the vertex at (0, 0) passes through (-1, 0). We'll say that the "height" of this triangle is 1, where by height we mean the length of the vertical dropped from the top vertex.

Then the set of points of vertical distance at least r from the top of the original triangle form a triangle of height 1-r, similar to the original triangle. Thus

$$ Prob(hbox{vertical distance from top } &gt; r) = (1-r)^2 $$

and this gives the distribution. In particular the expected value of the vertical distance from a random point to the top of the triangle (after the rescaling given above) is 1/3.

If you want to pick a random direction, though, then this gets a lot harder because the rescaling step will act differently for different directions.

mg.metric geometry - Routh's theorem in three dimensions

The following paper establishes a generalization of Routh's theorem to 3 dimensions:

Semyon Litvinov,
František Marko, Routh’s theorem for tetrahedra.Geom. Dedicata 174 (2015), 155–167

First, a new tetrahedron is determined by its vertices, which are points on 4 edges of the original one. The authors start with a tetrahedron $ABCD$, choose points $M, N, K, L$ on the edges $AB$, $BC$, $CD$, $DA$ which cut these edges in ratios $x, y, z, t$ respectively, and give an explicit formula for the ratio of the volumes of $KLMN$ and $ABCD$ in terms of $x, y, z, t$. Another tetrahedron is enclosed by the planes $ABK, BCL, CDM, DAN$ and the authors find explicitly the corresponding volume ratio.

A follow-up paper is available on the ArXiv and contains $n$-dimensional generalizations and interesting bibliographical remarks.

gn.general topology - how slow can the dimension of a product set grow?

Let us define the following "dimension" of a Borel subet $B subset mathbb{R}^k$:

$dim(B) = min{n in mathbb{N}: exists K subset mathbb{R}^n, ~{rm s.t.} ~ B sim K}$,

where $sim$ denotes "homeomorphic to". Obviously, $0 leq dim(B) leq k$.

I have three questions: Given a $B subset mathbb{R}$,
1) As $k to infty$, how slow can $dim(B^k)$ grow? Can we choose some $B$ such that $dim(B^k) = o(k)$ or even $O(1)$?
2) Will it make a difference if we drop the Borel measurability of $B$ or add the condition that $B$ has positive Lebesgue measure?
3) Does this dimension-like notion have a name? The dimension concepts I usually see are Lebesgue's covering dimension, inductive dimension, Hausdorff dimension, Minkowski dimension, etc. I do not think the quantity defined above coincides with any of these, but of course bounds exist.

Thanks!

inequalities - A plausible inequality.

The following proof is a bit heavy-handed; I'm sure you it can be simplified. Assume $a_1=1, a_n=0$ as suggested above and write:

Write $$F(x,y) = sum_{i=1}^n a_i(x_i^2-y_i^2)$$, $$G(x,y)=F(x,y)^2+langle x,yrangle^2.$$
Let $(x,y)in S^{n-1}times S^{n-1}$ be a point where $G$ is maximized, where we may assume that for each $i$ at least one of $x_i,y_i$ is non-zero. It is clear that $-sum_i y_i^2 leq F(x,y) leq sum_i x_i^2$ so we may also assume $langle x,yrangle neq 0$.

By the method of Lagrange multipliers there exist $xi,eta$ such that for all $i$
$$ 4a_i x_i F+2langle x,yrangle y_i=2xi x_i$$ and
$$ -4a_i y_i F+2langle x,yrangle x_i=2eta y_i.$$

Multiplying the first equation by $x_i$, the second by $y_i$, adding the two and summing over $i$ gives
$ 4G = 2(xi+eta)$. Multiplying the second equation by $y_i$, the first by $x_i$ and adding gives $$ langle x,yrangle (y_i^2+x_i^2) = (xi+eta)x_i y_i = 2Gcdot x_i y_i. $$ By assumption one of $x_i,y_i$ is non-zero. Dividing by the square of that number we see that the quadratic $$langle x,yrangle t^2 - 2G t + langle x,yrangle = 0$$ has a real root. Evaluating the discriminant it follows that $$ G^2 leq langle x,yrangle^2 leq 1.$$

reference request - Fundamental groups of noncompact surfaces

I just ran across this question, and thought I would give a precise version of the proof Ilya suggested. I believe I learned this proof in Richie Miller's topology course, Michigan State University, 1977 or so.

Choose a triangulation of the surface $S$, equipped with the simplicial metric. Choose a maximal one-ended subtree $T$ of the dual 1-skeleton $S^{(1)}$. The subtree $T$ contains every dual $0$-cell, that is, the barycenter of every 2-simplex. Also, $T$ contains dual 1-cells crossing certain $1$-simplices. Let $U$ be the union of the open 2-simplices and open 1-simplices that contain a point of $T$. The metric completion of $U$, denoted $bar U$, is a closed disc with one boundary point removed, and so there is a deformation retraction from $bar U$ onto its boundary $partial bar U$. Attaching $bar U$ to $S - U$ in the obvious way to form the surface $S$, the deformation retraction $bar U to partialbar U$ induces a deformation retraction of $S$ onto $S-U$, wnich is a subcomplex of the 1-skeleton.

By the way, the subtree $T subset S^{(1)}$ can be constructed by an explicit process. Enumerate the dual $0$-cells $v_1,v_2,ldots in S^{(1)}$. Construct one-ended subtrees $T_1,T_2,ldots subset S^{(1)}$ as follows. $T_1$ is any proper ray based at $v_1$. If $v_n in T_{n-1}$ then $T_n = T_{n-1}$. If $v_n notin T_{n-1}$, let $T_n$ be the union of $T_{n-1}$ with any arc $alpha subset S^{(1)}$ having one endpoint at $v_n$ and intersecting $T_{n-1}$ in its opposite endpoint. Each $T_n$ is a one-ended tree by induction, and since the radius $r$ neighborhood of $v_1$ in $T_n$ stabilizes as $n to infty$, it follows that $T = cup_n T_n$ is a one-ended subtree of $S^{(1)}$, and it is maximal because it contains each $v_i$.

I think this proof generalizes to any dimension, to give the theorem that Igor Belegradek refers to.

--- Edited to simplify and clarify the argument ---

ag.algebraic geometry - finite surjective l.c.i morphism is flat

Let $X,Y$ be locally Noetherian schemes. Let $f:Xto Y$ be a finite, surjective, and locally complete intersection morphism, i.e., locally it can be decomposed as regular immersion followed by a smooth morphism.
Recall: an immersion $Xto Y$ is called a regular immersion at a point $x$ if $mathcal{O}_{X,x}$ is isomorphic as $mathcal{O}_{Y,y}$-module to $mathcal{O}_{Y,y}$ modulo an ideal $I$ generated by a regular sequence of elements of $mathcal{O}_{Y,y}$.

Question: prove that $f$ is flat. In particular, $f$ will be a simultaneously open and closed morphism.

nt.number theory - What primes divide the discriminant of a polynomial?

First, when you say "it is symmetric", you probably mean that the polynomial $P(t) = a_n t^n + ... + a_1 t + a_0$ satisfies $a_{n-i} = a_i$ for all $0 leq i leq n$, not that the matrix is symmetric, since it is the former condition which implies that the set of roots is invariant under taking reciprocals (and also that $0$ is not a root). Such a polynomial is more commonly called palindromic.

The connection with the matrix seems unhelpful, because every polynomial is the characteristic polynomial of some matrix, e.g. its companion matrix. (It could possibly become helpful if you had some additional information about the matrix.)

You ask whether one can tell which primes divide the discriminant from the coefficients of the polynomial. The answer is a resounding yes, although perhaps not in a way which will be satisfying to you: you can compute the discriminant directly from the coefficients of the polynomial and then you can factor it! The formula you gave is actually not very good for computing the discriminant: for that it is better to use

$operatorname{disc}(P) = (-1)^{frac{(n)(n-1)}{2}} frac{operatorname{Res}(P,P')}{a_n}$,

where $P'(t)$ is the derivative and $operatorname{Res}$ is the resultant, computed using its interpretation as the determinant of the Sylvester matrix.

[Thanks to Michel Coste for pointing out that the discriminant is not quite equal to the resultant of $P$ and $P'$ when $P$ is not monic.]

gt.geometric topology - Formulas for vector fields on Grassmannians?

Pick an even dimensional real vector space $V$ of dimension $n$ and fix a symplectic form $omega$ on $V$. Look at it as a map $omega:Votimes Vtomathbb R$ by extending it from $Lambda^2V$ to $Votimes V$ as zero on the symmetric part. Fix also an inner product $langlemathord-,mathord-rangle$ in $V$.

Let $k$ be odd and such that $1leq kleq n$.

Let $Wsubseteq V$ be an $k$-dimensional subspace, and let $W^perp$ and $W^{perpomega}$ be the subspaces orthogonal to $W$ with respect to $langlemathord-,mathord-rangle$ and to $omega$, respectively. We know that $dim W^perp=dim W^{perpomega}=dim V-dim W$.

The restriction $omega|_{Wotimes W^perp}:Wotimes W^perptomathbb R$, which I will write for simplicity just $omega_W$, is not zero. Indeed, if it were zero, we would have that $W^perp$ is contained in $W^{perpomega}$, so in fact these two orthogonal subspaces would be equal, and in consequence we would have that $Wcap W^{perpomega}=Wcap W^perp=0$. This would tell us that $W$ is in fact a symplectic subspace of $V$, which is absurd because it is odd dimensional.

Now $omega_W$ is an element of $hom(Wotimes W^perp,mathbb R)$, which identifies canonically with $hom(W,hom(W^perp,mathbb R))$. The inner product $langlemathord-,mathord-rangle$ restricts to an inner product on $W^perp$ which allows us to identify canonically (because the inner product is fixed!) $hom(W^perp,mathbb R)$ with $W^perp$. After all these identifications, we have a non zero vector $omega_W$ in $hom(W,W^perp)$.

Now, as explained in an answer to a MO question, $hom(W,W^perp)$ parametrizes a neighborhood of $W$ in $G(n,k)$, so it also can be identified with the tangent space to $G(n,k)$ at $W$.

We thus see that the rule $Wmapsto omega_W$ gives a non-zero tangent vector field.

ag.algebraic geometry - How the complex conjugation on sheaves of modules is defined?

(Probably some basic question, but I've never worked in the real world.)

Let $Xsubsetmathbb{P}^n_mathbb{C}$ be a complex variety with the complex conjugation $tau:Xto X$. So $tau$ acts on $mathcal{O}_X(k)$ too.

Suppose $F$ is a sheaf of modules with prescribed embedding of modules of its local sections: $F(U)subset mathcal{O}^{oplus d}(U)$.
The complex conjugation acts on $mathcal{O}^{oplus d}(U)$, hence the images of $F(U)$ are defined. Hence the image of $F$ too.

Now should check that this is compatible with exact sequences etc...

Other ways to define the action of complex conjugation?

References?

graph theory - How much must deleting a spanning tree reduce edge-connectivity?

Suppose you have a 100-edge connected graph (e.g. an infrastructure network). You want to delete the edges of a spanning tree, any spanning tree you choose (e.g. to sell a connected subnetwork). What is the most edge-connectivity you can guarantee in the remaining graph?

Formally: let $r(k)$ be $$min_{G: k textrm{ edge-connected}} ~~ max_{T} ~~ textrm{edge-connectivity}(G backslash E(T))$$ where $T$ ranges over spanning trees of $G$, then what is $r(k)$?

I feel that in general, starting from a $k$-edge-connected graph, one should be able to leave edge-connectivity $k-o(k)$. However, the only useful bound I see so far is that "Every $2t$-edge-connected graph has $t$ spanning trees" implies $r(k) ge lfloor k/2 rfloor - 1$. This is far from tight with respect to the best upper bound I can prove, $r(k) le k-3$.

ho.history overview - Query: Year of Death of Three Mathematicians

I need the year of death of the following mathematicians all of whom are written up in R.C.Archibald's book Mathematical Table Makers.

Carl Burrau, b. 1867, d. ???? - Danish, astronomer and actuary

Herbert Bristol Dwight, b. 1885, d. ???? - American, tables of integrals

Alexander John Thompson, b. 1885, d. ????, British, statistician, BAASMTC

Thanks for any insight.

Cheers, Scott