computational complexity - Are there any interesting examples of random NP-complete problems?

Important update (Oct. 6, 2010): I'm pleased to say that I gave the "random 3SAT" problem in the OP to Allan Sly, and he came up with a simple NP-hardness proof. I've posted the proof to my blog with Allan's kind permission.

---

Sorry that I'm extraordinarily late to this discussion!

Regarding Tim's specific question: if we stick enough clauses in our instance that every 3SAT instance (satisfiable or not) occurs as a subformula with high probability, then certainly the resulting problem will be NP-hard. Indeed, it would suffice to have a large enough set of clauses that we can always find a subformula that can serve as the output of one of the standard reductions. On the other hand, I don't know of any techniques for proving NP-hardness that are tailored to the setting Tim has in mind -- it's a terrific question!

Since I can't answer the question he asked, let me talk for a while about a question he didn't ask (but that I, and apparently some of the commenters, initially thought he did). Namely, what's known about the general issue of whether there are NP-complete problems that one can show are NP-hard on average (under some natural distribution over instances)?

(1) The short answer is, it's been one of the great unsolved problems of theoretical computer science for the last 35 years! If there were an NP-complete problem that you could prove was as hard on average as it was on the worst case, that would be a huge step toward constructing a cryptosystem that was NP-hard to break, which is one the holy grails of cryptography.

(2) On the other hand, if you're willing go above NP-complete, we know that certain #P-complete problems (like the Permanent over large finite fields) have worst-case/average-case equivalence. That is to say, it's exactly as hard to compute the permanent of a uniform random matrix as it is to compute the permanent of any matrix, and this can be proven via an explicit (randomized) reduction.

(3) Likewise, if you're willing to go below NP-complete, then there are cryptographic problems, such as shortest lattice vector (mentioned by Rune) and discrete logarithm, that are known to have worst-case/average-case equivalence. Indeed, this property is directly related to why such problems are useful for cryptography in the first place! But alas, it's also related to why they're not believed to be NP-complete. Which brings me to...

(4) We do have some negative results, which suggest that worst-case/average-case equivalence for an NP-complete problem will require very new ideas if it's possible at all. (Harrison was alluding to these results, but he overstated the case a little.) In particular, Feigenbaum and Fortnow showed that, if there's an NP-complete problem that's worst-case/average-case equivalent under randomized, nonadaptive reductions, then the polynomial hierarchy collapses. (Their result was later strengthened by Bogdanov and Trevisan.) There are analogous negative results about basing crytographic one-way functions on an NP-complete problem: for example, Akavia, Goldreich, Goldwasser, and Moshkovitz (erratum). At present, though, none of these results rule out the possibility of a problem being NP-complete on average under the most general kind of reductions: namely, randomized adaptive reductions (where you can decide what to feed the oracle based on its answers to the previous queries).

(5) Everything I said above implicitly assumed that, when we say we want an average-case NP-complete problem, we mean with a distribution over instances that's efficiently samplable. (For example, 3SAT with randomly generated clauses would satisfy that condition, as would almost anything else that arises naturally.) If you allow any distribution at all, then there's a "cheating" way to get average-case NP-completeness. This is Levin's universal distribution U, where each instance x occurs with probability proportional to $2^{-K(x)}$, K(x) being the Kolmogorov complexity of x. In particular, for any fixed polynomial-time Turing machine M, the lexicographically-first instance on which M fails will have a short description (I just gave it), and will therefore occur in U with large probability!

(6) If you're willing to fix a polynomial-time algorithm M, then there's a beautiful result of Gutfreund, Shaltiel, and Ta-Shma that gives an efficiently-samplable distribution over NP-complete problem instances that's hard for M, assuming $NP nsubseteq BPP$. The basic idea here is simple and surprising: you feed M its own code as input, and ask it to find you an instance on which it itself fails! If it succeeds, then M itself acts as your sampler of hard instances, while if it fails, then the instance you just gave it was the hard instance you wanted!

(7) Finally, what about "natural" distributions, like the uniform distribution over all 3SAT instances with n clauses and m~4.3n variables? For those, alas, we generally don't have any formal hardness results.

big list - Books you would like to see translated into English.

Probably most of the works from Oskar Perron. It has been mentioned already Die Lehre von den Kettenbrüchen, both volumes, but we could also ask for Irrationalzahlen or any of the other works from Perron.
Also worth being mentioned, for applied mathematicians, are the works of Grigory Isaakovich Barenblatt, previous to 1994; this is because Barenblatt has consistently worked about scaling phenomena, but from about the beginnings of the 1990's he began to do it on his own, whereas earlier work includes the participation of other marvelous mathematicians, like Z'eldovich; or even works on his own, but it is interesting to compare the evolution of his ideas. So, the name of books with his participation previous to the 1990's, and to my knowledge, not translated into English:
* Ja, B Zeldovich, G. I. Barenblatt, V. B. Librovich, G. M. Maxvikadze "Matematicheskaja teorija gorenija i vsriva", 1980
* G. I. Barenblatt, "Podobie, avtomodelnoct, promezhutochnaja asimptotika: teorija i prilozhenija k geofizicheskoi gidrodinamike", 1982
* A. P. Licitsin, G. I. Barenblatt "gidrodinamika i osadkoobrasovanie", 1983
* G. I. Barenblatt, V. N. Entov, V. M. Rizhik, "Dvizhenie zhidkocteii i gazov v prirodnix plactax" 1984
* G. I. Barenblatt, "Analiz razmernosteii" . Uch. pos. M.: MFTI, 1987. 168 с. (I think this last work made it to English under the translation as "Dimensional Analysis", but in that case I saw it only once, at the library of the Department of Applied Mathematics and Theoretical Physics -DAMTP-of Cambridge, UK, many years ago and is likely out of print anyway, plus the edition, to my knowledge was not revised; on top of that, DAMTP changed from Silver Street to Wilberforce road, and I have no idea if that book survived the moving, if indeed was at that library).

Notice also, that in the Nachlass (the collection of manuscripts, left after the death of an academician, and of course in particular a mathematician) of people like Bernhard Riemann or Ernst Zermelo, there might be still some untranslated documents, but then again they also need to be interpreted in a way that could be meaningful, and this because they are not finished, published or even unpublished works, but sketches of something not fully developed.

gr.group theory - Rational points

Question (edited here)

Let $G$ be an affine algebraic group defined over a field $k$ of characteristic zero. Is it possible for $|G(k)|=1$, even if $G$ is not trivial?

As shown by David Speyer in the comments, if $dim G=0$ then yes. For example, let $G$ be the solutions to $z^3-1$. Then over $|G(mathbb{Q})|=1$, but $|G(mathbb{C})|=3$ and hence $G$ is not trivial.

On the other hand, the comments by Brian Conrad show that if $dim G geq 1$, then $|G(k)|not=1$.

I think this proves it: Since the identity component of $G$ is a connected affine algebraic group over $k,$ it suffices to prove this for $G$ connected. Then, since we are in characteristic 0, $G$ is isomorphic (as a variety, but not as an algebraic group) to $(G/G_u) times G_u$ where $G_u$ is its unipotent radical. The unipotent radical is likewise isomorphic to an affine space, and $G/G_u$ is reductive. By the Bruhat-decomposition $G/G_u$ contains an affine open subset whose $overline{k}$-points are isomorphic to $(overline{k}^*)^n times overline{k}^m$ where $overline{k}$ is an algebraic closure of $k$.

latex - Sources for Bibtex entries

If you use a mac, BibDesk is fantastic: among other really nice features, it lets you find your book/article/etc on your choice of free sites (ACM, arXiv, CiteULike, Google Scholar, HubMed, SPIRES) or subscription sites (IEEE Xplore, MathSciNet, Project Euclid, Zentralblatt Math) and then once you've found the item, it takes one click to import the citation into the database. The database can also store electronic copies of articles (if available) referenced to the citation.

So for example, I would open BibDesk, click on the icon that says Web, click on "MathSciNet". Within the program I see the MathSciNet page (assuming I'm at work where I have access). Type in the search terms Hartshorne and Geometry, and up comes 8 citations I could import. One of them is Algebraic Geometry from 1977, so I would click on the button that says "import". BibDesk does all the other work.

While writing a paper, just drag and drop the citations onto your LaTeX document to embed cite{blah} with the appropriate cite key (at least if you're using TeXShop).

When you're ready to stick a bibliography into your paper, select the relevant articles in the BibDesk database and export them into a BibTeX file. It's super easy.

Finding questions between functional analysis and set theory

Though this is a little more advanced, there is actually some very exciting research right now at the intersection of descriptive set theory, ergodic theory, and von Neumann algebras. It is quite striking that the three areas have powerful tools for looking at similar problems, and yet tend to be applicable in different cases. For a nice introduction to some of these ideas from a more set-theoretical point of view I would say check out
"Topics in Orbit Equivalence" by Kechris and Miller.

http://www.springerlink.com/content/0pwfmbrandag/

Here is a link where you can download it (though you might need a subscription but many universities will have it so it should work on a department computer.) It is actually quite elementary, you need some basic descriptive set theory and measure theory, but arrives at quite deep theorems.

math philosophy - Were Bourbaki committed to set-theoretical reductionism?

A set-theoretical reductionist holds that sets are the only abstract objects, and that (e.g.) numbers are identical to sets. (Which sets? A reductionist is a relativist if she is (e.g.) indifferent among von Neumann, Zermelo, etc. ordinals, an absolutist if she makes an argument for a priviledged reduction, such as identifying cardinal numbers with a equivalence classes under equipollence). Contrasting views: classical platonism, which holds that (e.g.) numbers exist independently of sets; and nominalism, which holds that there are no abstract particulars.

I'm interested in the relationship between "structuralism" as its understood by philosophers of science and mathematics and the structuralist methodology in mathematics for which Bourbaki is well known. A small point that I'm hung up on is the place of set theory in Bourbaki structuralism. I'm weighing two readings.

• (1) conventionalism: Bourbaki used set theory as a convenient "foundation", a setting in which models of structures may be freely constructed, but "structure" as understood in later chapters is not essentially dependent on the formal theory of structure developed in Theory of Sets,


• (2) reductionism: sets provide a ground floor ontology for mathematics; mathematicians study structures in the realm of sets.

In favor of conventionalism:

• (a) Leo Corry's arguments in “Nicolas Bourbaki and the Concept of Mathematical Structure” that the formal structures of Theory of Sets are to be distinguished from and play only a marginal role in the subsequent investigation of mathematica

ct.category theory - Does any tensor category correspond to a bialgebra?

I'd like to explain Bruce's answer a bit more. The fusion categories Bruce mentioned have non-integer Frobenius-Perron dimensions, so it is very easy to see that they are not categories of finite dimensional modules over a bialgebra. E.g. one of the simplest of them, the so called Yang-Lie category, has simple objects $1,X$ with $X^2=X+1$. So if $X$ were a finite dimensional representation of a bialgebra, then the dimension of $X$ would be the golden ratio, which is absurd.

This, however, can be fixed if we allow weak bialgebras and weak Hopf algebras. In fact, any fusion category is the category of modules over a finite dimensional weak Hopf algebra, see arXiv.math/0203060.

As to Akhil's example (Deligne's categories), it is also true that they cannot be realized as categories of finite dimensional representations of a bialgebra (or even a weak bialgebra), but for a different reason. Namely, if X is a finite dimensional representation of a bialgebra, then the length of the object $X^{otimes n}$ is at most ${rm dim}(X)^n$, where ${rm dim}$ means the vector space dimension. But in Deligne's categories, the length of $X^{otimes n}$ grows faster as $nto infty$. Actually, in another paper, Deligne shows that if in a symmetric rigid tensor category over an algebraically closed field of characteristic zero, the length of $X^{otimes n}$ grows at most exponentially, then this is the category of representations of a proalgebraic supergroup, where some fixed central order 2 element acts by parity
(so essentially this IS the category of (co)modules over a bialgebra). This is, however, violently false in characteristic $p$, since if the root of unity $q$ is of order $p$, where $p$ is a prime, the the fusion categories for $U_q({mathfrak g})$ mentioned by Bruce admit good reduction to characteristic $p$, which are semisimple symmetric rigid tensor categories with finitely many simple objects and non-integer Frobenius-Perron dimensions.

A third very simple example of a tensor category not coming from a bialgebra is the category of vector spaces graded by a finite group $G$ with associator defined by a nontrivial $3$-cocycle. This category, however, is the category of representatins of a quasibialgebra (and also of a weak bialgebra, as mentioned above).

So the conclusion is as in the previous two answers: tensor categories are more general than bialgebras. More precisely, the existence of a bialgebra for a tensor category is equivalent to the existence of a fiber functor to vector spaces, which is an additional structure that does not always exist. And if it exists, it is often not unique, so you may have many different bialgebras giving rise to the same tensor category.

set theory - Reasons to believe Vopenka's principle/huge cardinals are consistent

Because of Goedel's Incompleteness Theorems, we know that
we cannot describe a complete axiomatization of
mathematics. Any proposed axiomatization $T$, if
consistent, will be unable to prove the principle Con(T)
asserting that $T$ itself is consistent, although we have
reason to desire this principle once we have committed
ourselves to $T$. Adding the consistency principle Con(T)
simply puts off the question to Con(T+Con(T)), and so on,
in a process that proceeds into the transfinite.

Thus, we come to know that there should be a transfinite
tower of theories above our favorite theories, transcending
them in consistency strength. The incompleteness theorems
imply that there is a tower of theories above PA, above
ZFC, each level transcending the consistency strength of
the prior levels.

How fortunate and wonderful that we have also independently
come upon such a tower of theories: the large cardinal
hierarchy. Numerous large cardinal concepts arose very
early in set theory, from the time of Cantor, before
Goedel's theorems and before the notion of consistency
strength was formulated. These large cardinal concepts
arose from natural set-theoretic questions in infinite
combinatorics: Can there be a regular limit cardinal? Can
there be a countably-complete measure measuring all subsets
of a set? Does every $kappa$-complete filter on a set
extend to a $kappa$-complete ultrafilter? And so on.

Eventually, it was realized that these large cardinal
notions separate into a very tall hierarchy, with the
property that from the larger cardinals, one can prove the
consistency of the smaller cardinals. For example, if
$kappa$ is the least Mahlo cardinal, then the universe
$H_kappa$ is a model of ZFC + there is a stationary
proper class of inaccessible cardinals + there are no
Mahlo cardinals. If $delta$ is the least measurable
cardinal, then $H_delta$ satisfies ZFC + there are a
proper class of Ramsey cardinals, but no measurable
cardinal.

Thus, the large cardinal hierarchy provides exactly the
tower of theories, whose levels transcend consistency
strength, that we knew should exist. And it does so in a
way that is mathematically robust and interesting, with its
foundations arising, not in some syntactic diagonalization,
but in mathematically fulfilling and meaningful questions
in infinite combinatorics.

The case of Vopenka's principle is just like this. VP is a
large cardinal axiom at the higher end of the large
cardinal hierarchy, implying the consistency of the
existence of supercompact cardinals, say, which are far
stronger than strong cardinals, which imply entire towers
of measurable cardinals, which imply numerous Ramsey
cardinals and so on down the line.

Illustrating the essential large cardinal nature, the VP
axiom is elegantly stated: for every proper class sequence
$langle M_alpha | alphaintext{ORD}rangle$ of first
order structures, there is a pair of ordinals
$alphaltbeta$ for which $M_alpha$ embeds elementarily
into $M_beta$. (It is equivalently stated in terms just of
graphs, if you like.) It's simple and clear---beautiful!
And the consequences are far-reaching and often profound,
as you have observed in category theory, in the way that VP
implies that the set-theoretic universe is regular and
organized.

These are the reasons you should be attracted to Vopenka's
principle. It is an elegant combinatorial principle, with
far-reaching consequences that interest you, which has not
yet been refuted.

In contrast, I find the philosophical heuristics that seek
to justify the large cardinal axioms, on the grounds of
reflection or some other means, to be so much hot air ultimately unsatisfying.
These arguments are not mathematically sound, and cannot be
made to be, by the Incompleteness Theorems.
Philosophically, they seem much more like rationalizations
after the fact. For example, even at the much lower (and
therefore seemingly easier-to-justify) level of
inaccessible cardinals, one sometimes hears an appeal to
reflection type views, that since we have no definable
unbounded map from a set into the ordinals, that there
should be a level $V_kappa$ of the universe also with this
feature, and that such a level would be inaccessible
cardinal. Of course, the conclusion outstrips the argument,
with the conclusion seeming to justify at most
$V_kappamodels$ZFC, which is a weaker notion, and the
meta-reflection principle appealed to amounts anyway to a
large cardinal principle of its own.

Ultimately, we must recognize the uncertain nature of all
our mathematical enterprise. As our hypotheses rise higher
in the large cardinal hierarchy, we must become less sure
of consistency---perhaps they will be shown to be
inconsistent. This issue arises even at the lowest levels
of our mathematical axiomatizations, for we may find at any
time (as mentioned in a recent MO
question)
that even PA is inconsistent. As Woodin says, we all have
in our minds the image of a railway line, lined by a
sequence of telegraph poles, proceeding into infinity; but
when the physicists tell us that the universe is finite, we
realize that this picture is pure imagination. Perhaps it
is simply inconsistent? So skepticism about consistency has
nothing especially to do with the infinite.

Meanwhile, the large cardinal axioms are fascinating and
have fascinating consequences. Let's seek out the boundary
of consistency, with an attitude tempered by the
realization that we may find inconsistency.

In summary, we cannot ever be sure that our axioms are
consistent, and we know that above the mathematical theory
about which we may be sure, there is a tall tower of
theories whose levels transcend consistency. Among them are
fascinating theories that are elegantly stated with
far-reaching consequences, and which we have not yet
refuted. So let's study them! Let's find the boundary
between consistency and inconsistency!

pr.probability - What is the difference between a homogeneous stochastic process and a stationary one?

A process is (strictly) stationary if any sequence of n consecutive points has the same distribution as any other sequence of n consecutive points. There are weaker definitions, for example weak stationarity is based only on the first two moments.

A (discrete valued) process is homogeneous if the transition probability between two given state values at any two times depends only on the difference between those times.

However, some references uses "homogeneous" rather loosely and confuse the two concepts.

ag.algebraic geometry - Geometric interpretation of filtered rings and modules

To a filtered algebra $(A,F)$ one can assign its Rees algebra $R=bigoplus_i F_iA$. It is a graded algebra containing the algebra of polynomials in one variable $mathbb{C}[t]$ naturally embedded as the subalgebra generated by the element $tin R_1$ corresponding to the element $1in F_1A$. So the algebra $R$ defines a $mathbb{C}^*$-equivariant quasi-coherent sheaf of algebras $mathcal{R}$ over the affine line $operatorname{Spec}mathbb{C}[t]$. The algebra $A$ can be recovered as the fiber of $mathcal{R}$ at the point $t=1$, and the associated graded algebra $operatorname{gr}_FA$ is the fiber of $mathcal{R}$ at $t=0$. Filtered $A$-modules correspond to $mathbb{C}^*$-equivariant quasi-coherent sheaves of modules over $mathcal{R}$.

The algebra $R$ is a torsion-free $mathbb{C}[t]$-module, so the quasi-coherent sheaf $mathcal{R}$ over $operatorname{Spec}mathbb{C}[t]$ has to be torsion-free. This description does not take into accout the issue of completeness of the filtration $F$ (in case it extends also in the decreasing direction), which requires a separate consideration.

nt.number theory - Bound on the number of prime factors of logarithmically rough numbers

The intuition is that $log_{clog N}N=frac{log N}{log(clog N)}=frac{log N}{log c+loglog N}$ which is asymptotically $frac{log N}{loglog N}$. For this to work, we need that the kth prime for $k=frac{log N}{log(clog N)}+pi(clog N)approxfrac{log N}{loglog N}$ to be 'close' to $clog N$ -- actually, any constant multiple of $log N$ will do.

$p_kapproxfrac{log N}{loglog N}logfrac{log N}{loglog N}approxlog N$, so $log_{p_k}Napproxfrac{log N}{loglog N}$, as desired. This could probably made explicit with Rosser's theorem and/or Dusart's various bounds on $p_n$ and $pi(n)$.

nt.number theory - Density results for equality of Galois/automorphic representations

Firstly, at the beginning of the question you are missing irreducibility/cuspidality assumptions. If $rho_1$ and $rho_2$ are $ell$-adic Galois reps with the same char poly in a set of primes of density 1, then you can only deduce their semisimplifications are isomorphic. A counterexample to your statement would be given by $rho_1=1+omega$ ($omega$ the cyclotomic character) and $rho_2$ some non-split extension coming from Kummer theory (taking $ell$-poower roots of some prime number $p$ for example). Of course you knew that already.

On the automorphic side you make "the same slip", well, a related slip. If $chi$ and $psi$ are two Grossencharacters and their ratio is the norm character at some place $v$ (or possibly even infinitely many, or even all $v$), then the induction of $chi+psi$ from the Borel to $GL_2(mathbf{A})$ is reducible, and any Jordan-Hoelder factor (which by definition means a tensor product of J-H factors of the local inductions) ramified at all but finitely many places is an automorphic representation. So now you can build two non-cuspidal automorphic representations which are isomorphic at all but one place (and such that the local components don't even have the same dimension at the bad place) easily. Of course for cuspidal representations you have strong multiplicity 1 theorems.

Passing remark: it is a source of some confusion to me as to why these errors are "similar" but on the other hand they don't "biject". The problem is that on the Kummer theory side, if you allow ramification at two primes, you get a whole projective line of non-isomorphic Galois representations (all with the same semisimplificiation). On the automorphic side the amount of control you have is much more combinatorial (you can change a finite set of places from trivial to Steinberg and that's it). So $pi$ and $rho$s don't match up (so Toby Gee and I only conjecture that given any (EDIT: algebraic) $pi$ one expects a semi-simple $rho$, and nothing more, and for $GL_n$ this observation is no doubt much older).

OK so after these pedantic remarks, that you no doubt knew anyway, but could have avoided if you'd put "irreducible" and "cuspidal" in the appropriate places, we move on to the far more interesting question of whether one can do better than multiplicity 1. And your hunch is correct. First you should do the following exercise on the Galois side: if $rho_1$ and $rho_2$ are two irreducible 2-dimensional representations of a finite group $G$, and their traces agree on a set $S$ in $G$ of density greater than 7/8, then $rho_1$ and $rho_2$ are isomorphic. Big hint: orthogonality relations. Next you should convince yourself that 7/8 is optimal in this result Big hint: D_8 x D_8. (EDIT: slightly simpler is D_8 x C_2---here D_8 has 8 elements). So now for silly Artin representation reasons you can't expect to beat 7/8 (like you can't expect to beat 1/2 in the GL_1 case as in Jared's comment).

So now the great news is that Dinakar Ramakrishnan proved an analogue on the automorphic side! At least in some cases. See the appendix to "$l$-adic representations associated to modular forms over imaginary quadratic fields. II." by Richard Taylor (Inventiones 116).

As for your second question though, it's completely hopeless. Even for $GL_1$ your hope is (provably) way out, so for $GL_2$ one can perhaps construct "Eisenstein" counterexamples (induced from non-automorphic characters of $GL_1$). The first objection is that $pi_p$ can be ramified for infinitely many $p$, making you dead in the water. But even if $pi_p$ is unramified for all $p$ you've still got no chance. Let me stick to $GL_1/mathbf{Q}$. The point is that every Grossencharacter for $GL_1/mathbf{Q}$ is the product of a finite order character $chi$ (a Dirichlet character) and $||.||^s$, so you can recursively construct characters of $mathbf{Q}_p^times$ each of which is totally at odds with everything that came before. For example lets send $Frob_2$ to 1. Now let's write down all the solutions to $2^s.zeta=1$, with $zeta$ a root of unity and $s$ a complex number. There are only countably many values of $s$ in this list. So choose $s$ not in the list and send $Frob_3$ to $3^s$. Now knock off countably many more $s$ and send $Frob_5$ to $5^s$ for $s$ in neither list. We are making a collection of representations here that are pairwise completely incompatible! This is only one of the many obstructions. For example, for cuspidal automorphic representations there are Weil bound obstructions (Ramanujan conjecture) and arithmeticity obstructions in the holomorphic case---all deep theorems or conjectures about automorphic forms in some cases that can easily be violated if we're allowed to build $pi$ locally. These arguments trivially show that the set of automorphic $pi$s have density zero (and "a very small zero" at that) amongst all the $pi$s. In fact here's a much cleaner objection for $GL_2$: if you stick to cuspidal automorphic representations with a fixed central character then there are only countably many! But you have uncountably many choices at each local place! So it's completely hopeless I think.

Is it possible to use linear programming to solve this problem?

I am trying to write software to minimize pricing for cell phone subscription services, ie: choose the optimum plan for each customer in a large group.

Could someone comment on whether this is possible via linear programming?

Here is a description of the problem (the numbers in the examples may not be realistic so try to ignore that):

Base Plan Options

Plan A: 200 Voice minutes, 10 Text Messages, 10 MB Data  =  $25    
    Plan B: 400 Voice minutes, 25 Text Messages, 25 MB Data  =  $40    
Plan C: 1000 Voice minutes, 50 Text Messages, 50 MB Data =  $65    
    ...   
    Plan F: 2500 Voice minutes, 150 Text Messages, 150 MB Data =  $95  

Charges for exceeding your plan (for all cases):

$.10 per voice minute  
    $.20 per text message  
$1.50 per MB Data

Optional Add-On Packages (added to Base Plan):

Free Weekends  $15  
    Free Evenings and Weekends (after 8PM)  $20  
Free Evenings and Weekends (after 6PM)  $35
    Text Message Package #1 (50 Text Messages)  $5  
Text Message Package #2 (150 Text Messages)  $10  
    Data Package #1 (20 MB Data)  $20    
Data Package #2 (50 MB Data)  $30  
    Chatty User Mixed Pack #1 (100 Minutes Voice, 100 Text Messages) $15  
Geeky User Mixed Pack #1 (50 Minutes Voice, 150 MB Data) $35  
etc, etc etc  

So if I have a set of detailed usage data for say 500 users, I want to figure out which combination of base plan (A, B, C ... F) each person should be on, as well as which add-on packages(s) they should have.

In the base packages and optional add-ons examples I gave, I was trying to make the point that there are so many overlapping options that brute force calculation of each option for each user is impractical.

So my question is, can this somehow be done efficiently via linear programming?
And if so, I would greatly appreciate any hints or direction on where an experienced software developer with no expertise in linear programming might start?

Update

Thanks for the helpful comments so far. Thanks to DoubleJay I now know this is an integer programming problem. And yes, I most definitely will use a 3rd party solver, I need one that is callable from .Net platform, so if anyone has any suggestions on an affordable one let me know.

Once I have the solver, figuring out how one declares this problem within is my next problem, so any tips on where one would begin learning would also be much appreciated.

(Am also trying stackoverflow, but thought there'd likely be more expertise here for this particular problem).

pr.probability - Geneology of survivors in a critical discrete Galton-Watson process

Hello. After flipping through a few textbooks on birth-death processes, I can't seem to find anything about genealogical distribution of survivors (conditioned on non-extinction). What I am looking for is a statement roughly of the type, "in generation n, there is probability at least P(j,k,n) that descendants have survived from at least k distinct members of generation j".

I'm interested in the critical case of the Galton-Watson process, where the number of descendents is i.i.d. with mean 1. If necessary, assume the distribution is Bin(r,1/r).

Also, my sample question about P(j,k,n) is just the easiest thing I could think to write down. But I would like to know how likely it is for there to exist a very uniformly distributed subpopulation of size roughly n in generation n.

mathematics education - Why does undergraduate discrete math require calculus?

In the context of college students, I agree with Alexander Woo's explanation. By the way, the best and the brightest often place out of calculus (that's the case at Yale, and I imagine it's not that much different at Berkeley), so the percentages of weak students at best schools aren't as dire as you might think.

Concerning the last question,

"Why isn't discrete mathematics offered to high school students without calculus background?"

Not only is that possible, but it had been the norm in the past within the "New Math" curriculum, when everyone had to learn about sets and functions in high school. This ended in a PR disaster and a huge backlash against mathematics, because generations of students were lost and got turned off by mathematics for life; some of them later became politicians who decide on our funding. Consequently, it was abandoned. (Apparently, calculus in HS was introduced as a part of the same package and survived.)

I'd be interested to know if there are any high school – college partnerships that offer discrete mathematics to H.S. students with strong analytical skills, and how do they handle the prerequisites question.

ag.algebraic geometry - Are all parametrizations via polynomials algebraic varieties?

Suppose that we have a parametrization via polynomials as follows:

$$tlongrightarrow (f_1(t),ldots,f_n(t)),$$

where $t$ is a vector in $mathbb{C}^r$ and $f_i$ are polynomials of arbitrary degree.

Can we always find equations such that the image is an affine algebraic variety?

The question is motivated by Exercise 1.11 in Hartshorne:

Let $Ysubseteq A^3$ be the curve given parametrically by $x = t^3, y= t^4, z = t^5$. Show
that $I(Y)$ is a prime ideal of height 2 in $k[x,y,z]$ which cannot be generated by
2 elements.

I am not interested in the exercise in particular. Finding the variety is easy sometimes, for instance $trightarrow (t^2,t^3)$ is given by $I(x^3-y^2)$.

I am looking for a result which says that the image is always an affine algebraic variety AND a procedure to find the ideal.

gt.geometric topology - Mappings of mapping class groups

Your question (1) is pretty classical -- the Birman Hilden Annals paper from 1973 essentially answers it, no? I mean, they don't deal with the non-orientable case in their paper as far as I recall but the techniques still work.

Re (3), your notion of mapping class group for a surface with boundary would typically be called the mapping class group of a closed surface with marked points, in the literature I'm familiar with, denoted something like $MCG(X,n)$ for a closed surface $X$ and $n$ marked points -- in your case they would be circle boundary components.

In that regard there are extensions ($X$ a boundaryless surface)

$pi_1 Diff(X) to pi_1 C_n X to MCG(X,n) to MCG(X) to 0$

$C_n(X)$ is the configuration space of $n$ points in the surface $X$.

$pi_1 Diff(X)$ is typically trivial but there are some non-trivial cases like the torus, sphere $mathbb RP^2$, the Klein bottle. Some of these special cases give you injectivity $MCG(X,n) to MCG(X)$ for $n$ small, but not many.

Anyhow, it's a natural map and is frequently useful. Are you really more interested in knowing exactly when there is such an embedding or not, or are you more interested in general relations? ie: do you have a reason for wanting to know the answer to these questions?

co.combinatorics - Finding a set with the maximum number of finite alphabet strings within a fixed Levenshtein distance of one-another

Please consider the set of all possible strings of some finite size $M$ alphabet $Sigma$, $alpha$ $= a_1, a_2, ..., a_k, ..., a_n$, of length $|alpha| = L$. The Levenshtein distance (or 'edit distance') between any two strings, $D(a_{k1},a_{k2})$ = $p$, can be defined as the number of single-character insertions, deletions, or substitutions necessarily to transform one string, $a_{k1}$, into another, $a_{k2}$. We are forbidding the transposition operation, giving the $L = 3$ example: $D("abc", "cba")$ = $2$.

Let $(s_{p1}, s_{p2}, ..., s_{pk}, ..., s_{pm}) in S_p$, be a particular set that has the largest possible number of strings over the finite alphabet within a fixed Levenshtein distance, $p$, of one-another. Can we find a particular instance of $S_p$, or perhaps more easily $||S_p||$, for an arbitrarily sized alphabet, $Sigma$, and an arbitrary string length, $L$?

Perhaps this is more of a definition, but we know (trivially) that $||S_0|| = 1$. It seems to be true that $||S_1||$ increases in a linear way with $L$ and $M$. But there doesn't appear to be a nice growth relationship for $||S_p||$ as a function of $M$ and $L$ if $p > 1$.

Update - For the provided data, $||S_2||$ appears to have a closed-form solution of $4*(L-1)^2$ for a three-character alphabet, and a closed-form solution of $frac{3}{2}(5*(L-1)^2+(L-1))$ for a four-character alphabet.

Update - Does anyone know if this problem is in class NP, similar to the complexity of generating many types of error-correcting codes? I was hoping the case here would be different, as we're asking for less information...

---

A computer search yields:

For $L = 1$:
$$eqalign
{&(||S_0||,||S_1||)=cr
&qquad (1, 1) sim M = 2 cr
&qquad (1, 2) sim M = 3cr
&qquad (1, 3) sim M = 4cr}
$$

For $L = 2$:
$$eqalign
{&(||S_0||,||S_1||,||S_2||)=cr
&qquad (1, 2, 1) sim M = 2cr
&qquad (1, 4, 4) sim M = 3cr
&qquad (1, 6, 9) sim M = 4cr}
$$

For $L = 3$:
$$eqalign
{&(||S_0||,||S_1||,||S_2||,||S_3||)=cr
&qquad (1, 3, 4, 1) sim M = 2cr
&qquad (1, 6, 16, 8) sim M = 3cr
&qquad (1, 9, 33, 27) sim M = 4cr}
$$

For $L = 4$:
$$eqalign
{&(||S_0||,||S_1||,||S_2||,||S_3||,||S_4||)=cr
&qquad (1, 4, 9, 4, 1) sim M = 2cr
&qquad (1, 8, 36, 35, 16) sim M = 3cr
&qquad (1, 12, 72, 130, 81) sim M = 4cr}
$$

For $L = 5$:
$$eqalign
{&(||S_0||,||S_1||,||S_2||,||S_3||,||S_4||,||S_5||)=cr
&qquad (1, 5, 16, 11, 5, 1) sim M = 2cr
&qquad (1, 10, 64, 124, 80, 32) sim M = 3cr
&qquad (1, 15, 126, 410, 438, 243) sim M = 4cr}
$$

For $L = 6$:
$$eqalign
{&(||S_0||,||S_1||,||S_2||,||S_3||,||S_4||,||S_5||,||S_6||)=cr
&qquad (1, 6, 27, 28, 15, 6, 1) sim M = 2cr
&qquad (1, 12, 100, 306, 302, 192, 64) sim M = 3cr
&qquad (1, 18, 195, 942, 1938, 1458, 729) sim M = 4cr}
$$

For $L = 7$:
$$eqalign
{&(||S_0||,||S_1||,||S_2||,||S_3||,||S_4||,||S_5||,||S_6||,||S_7||)=cr
&qquad (1, 7, 40, 60, 39, 21, 7, 1) sim M = 2cr
&qquad (1, 14, 144, 612, 1030, 712, 448, 128) sim M = 3cr
&qquad (1, 21, 279, 1807, 5803, 6966, 5103, 2187) sim M = 4cr}
$$

For $L = 8$:
$$eqalign
{&(||S_0||,||S_1||,||S_2||,||S_3||,||S_4||,||S_5||,||S_6||,||S_7||,||S_8||)=cr
&qquad (1, 8, 56, 113, 97, 56, 28, 8, 1) sim M = 2cr
&qquad (1, 16, 196, 1074, 2716, 2575, 1792, 1024, 256) sim M = 3cr
&qquad (1, 24, 378, 3086, 13716, 28310, 23414, 17496, 6561) sim M = 4cr}
$$

For $L = 9$:
$$eqalign
{&(||S_0||,||S_1||,||S_2||,||S_3||,||S_4||,||S_5||,||S_6||,||S_7||,||S_8||)=cr
&qquad (1, 9, 74, 194, 216, 135, 84, 36, 9, 1) sim M = 2cr
&qquad (1, 18, 256, 1724, 5956, 8315, 6309, 4608, 2304, 512) sim M = 3 cr}
$$

For $L = 10$:
$$eqalign
{&(||S_0||,||S_1||,||S_2||,||S_3||,||S_4||,||S_5||,||S_6||,||S_7||,||S_8||)=cr
&qquad (1, 10, 95, 311, 448, 321, 210, 120, 45, 10, 1) sim M = 2cr}
$$

gr.group theory - Why are free groups residually finite?

Here is a direct proof for free groups.

Let $x_1,dots,x_m$ be the generators of our group. Consider a word $x_{i_n}^{e_n}dots x_{i_2}^{e_2}x_{i_1}^{e_1}$ where $e_iin{pm 1}$ and there are no cancellations (that is, $e_k=e_{k+1}$ if $i_k=i_{k+1}$).

I'm going to map this word to a nontrivial element of $S_{n+1}$, the group of permutations of $M:={1,dots,n+1}$. It suffices to construct permutations $f_1,dots,f_min S_{n+1}$ such that $f_{i_n}^{e_n}dots f_{i_2}^{e_2}f_{i_1}^{e_1}ne id_M$. For each $k=1,dots,n$, assign $f_{i_k}(k)=k+1$ if $e_k=1$, or $f_{i_k}(k+1)=k$ if $e_k=-1$. This gives us injective maps $f_1,dots,f_m$ defined on subsets of $M$. Assign yet unassigned values of $f_i$'s arbitrarily (the only requirement is that they are bijections). The resulting permutations satisfy $f_{i_n}^{e_n}dots f_{i_2}^{e_2}f_{i_1}^{e_1}(1)=n+1$.

Edit: As pointed out by Steve D in comments, this proof can be found in a book by Daniel E. Cohen, "Combinatorial group theory: a topological approach" (1989). The book can be found on the net if you are determined; the proof in on page 7 and in Proposition 5 on page 11.

---

Edit [DZ]: I have a hard time reading multiple subscripts, so here is an example of Sergei Ivanov's construction.

Take the word $cca^{-1}bc^{-1}a$. This has length $6$, so we will find a homomorphism to $S_7$ whose image of this word is nontrivial because it sends $1$ to $7$. We'll choose values of permutations so that the $k$th suffix sends $1$ to $k+1$:

Suffix 1: $a$

$alpha=bigg(begin{array}{} 1&2 &3 &4& 5& 6& 7 \ 2&?&?&?&?&?&? end{array} bigg)$

Suffix 2: $c^{-1}a$

$gamma=bigg(begin{array}{} 1&2 &3 &4& 5& 6& 7 \ ?&?&2&?&?&?&? end{array} bigg)$

Suffix 3: $bc^{-1}a$

$beta=bigg(begin{array}{} 1&2 &3 &4& 5& 6& 7 \ ?&?&4&?&?&?&? end{array} bigg)$

Suffix 4: $a^{-1}bc^{-1}a$

$alpha=bigg(begin{array}{} 1&2 &3 &4& 5& 6& 7 \ 2&?&?&?&4&?&? end{array} bigg)$

Suffix 5: $ca^{-1}bc^{-1}a$

$gamma=bigg(begin{array}{} 1&2 &3 &4& 5& 6& 7 \ ?&?&2&?&6&?&? end{array} bigg)$

Suffix 6: $cca^{-1}bc^{-1}a$

$gamma=bigg(begin{array}{} 1&2 &3 &4& 5& 6& 7 \ ?&?&2&?&6&7&? end{array} bigg)$

These conditions on $alpha, beta,$ and $gamma$ don't conflict, they can be extended to permutations, and then $gammagammaalpha^{-1}betagamma^{-1}alpha(1) = 7$.

gr.group theory - vanishing of certain product in group algebra

I think the answer is "if and only if the group $G$ is not cyclic". Why?

1) An element of $mathbb Cleft[Gright]$ is zero if and only if it acts as zero on each irreducible representation of $G$ (since $mathbb Cleft[Gright]$ is the direct sum of the endomorphism rings of the irreducible representations).

2) An element of $mathbb Cleft[Gright]$ acts on an irreducible representation of $G$ either as zero or as an automorphism (because each irreducible representation of $G$ is $1$-dimensional, since $G$ is abelian).

Hence, for a product of the form $prod_{gin S}left(1-gright)$ to be zero, where $S$ is some ordered list of elements of $G$, it is necessary and sufficient that for each irreducible representation of $G$, there exists some $gin S$ such that $1-g$ acts as zero on the representation, i. e. that $g$ acts as identity on the representation. Applied to a list $S$ containing all elements of $Gsetminus 1$ (maybe several times), this means that the product $prod_{gin S}left(1-gright)$ is zero if and only if no irreducible representation of $G$ is faithful. Easy manipulations with roots of unity show this to hold if and only if $G$ is not cyclic.

peano arithmetic - How would one even begin to try to prove that a simple number-theoretic statement is undecidable?

EDIT

Here is my problem. To prove that statement S is undecidable is to

(1) prove that one cannot prove S.

I think I understand the meaning of the second "prove". (It depends of course on the context.) But I don't understand the meaning of the first "prove".

A "solution" would be to replace (1) by

(2) give an informal proof showing that one cannot prove S,

or

(3) give an acceptable argument showing that one cannot prove S.

This seems to be in tune with the following quotation from Cohen's "Set theory and the Continuum Hypothesis" (p. 41):

We have now arrived at a rather peculiar situation. On the one hand $sim A$ is not provable in $Z_1$ and yet we have just given an informal proof that $sim A$ is true. (There is no contradiction here since we have merely shown that the proofs in $Z_1$ do not exhaust the set of all acceptable arguments.)

I think it would be an enormous progress to replace (1) by (2) or (3).

In other words, instead of talking about "proving" that some statements are undecidable, it would be wiser, I believe, to talk about giving "informal proofs", or "acceptable arguments", or "convincing evidence", ... that these statements are undecidable.

END OF EDIT

---

Here is, for what it's worth, my personal conviction on this.

If (like me) you don't believe that "you can't get something for nothing", then you don't believe in Gödel and Cohen's results.

The claim to "get something for nothing" is very openly expressed (in my opinion) by Cohen on page 39 of "Set theory and the Continuum Hypothesis":

The theorems of the previous section are not results about what can be proved in particular axiom systems; they are absolute statements about functions.

Cohen really says: "The theorems of the previous section are proved without invoking any axiom, that is, they are gotten for nothing". Or am I putting words in his mouth?

I think the key is to understand the respective STATUS of the various statements involved. In particular, a clear distinction should be made between mathematical and metamathematical statements.

I also think we should all make an effort to talk unemotionally about such questions.

soft question - Which mathematicians have influenced you the most?

There are mathematicians whose creativity, insight and taste have the power of driving anyone into a world of beautiful ideas, which can inspire the desire, even the need for doing mathematics, or can make one to confront some kind of problems, dedicate his life to a branch of math, or choose an specific research topic.

I think that this kind of force must not be underestimated; on the contrary, we have the duty to take advantage of it in order to improve the mathematical education of those who may come after us, using the work of those gifted mathematicians (and even their own words) to inspire them as they inspired ourselves.

So, I'm interested on knowing who (the mathematician), when (in which moment of your career), where (which specific work) and why this person had an impact on your way of looking at math. Like this, we will have an statistic about which mathematicians are more akin to appeal to our students at any moment of their development. Please, keep one mathematician for post, so that votes are really representative.

ag.algebraic geometry - What is the base change in number theory?

In number theory, base change of a scheme or a variety is with respect to the underlying ring or field, is viewing the same scheme/variety over an extended ring or field, but with the "same" set of equations.

For example given a curve over $mathbb Q$, it is also a curve over any number field. Or given a scheme over spectrum of $mathbb Z$ given by some equation, you can reduce it modulo a prime $p$ and obtain a scheme over $mathbb F_p$.

When you are dealing with group schemes, moduli, motives, etc., such notions carry over through base change, modulo technical details.

rt.representation theory - How to think about parabolic induction.

I have also been trying to understand the big picture here. As far as I can tell, the key point is that two parabolic subgroups $P$ and $Q$ of $G$ have conjugate Levis if and only if $Pbackslash G/Q$ contains an orbit which is the preimage of a single Bruhat cell in $Pbackslash G$ and $G/Q$.

Some more details: (My apologies if I have missed the point of the question and the following is already well understood to everyone (or just wrong!). I have tried to write down a general argument that would apply in various settings, but I am probably missing important features of the proof in any particular setting.)

Suppose $P$ and $Q$ are parabolic subgroups of $G$ with Levi factors $L$ and $M$ respectively (I would also prefer to think about the Levis as being subquotients of $G$). I will not assume $L$ and $M$ are related to begin with.

Subsets of the double coset space $Pbackslash G/Q$ give rise to functors from representations of $L$ to representations of $M$. Taking the whole of $Pbackslash G/Q$ corresponds to the functor $Res_{M,Q}^G Ind_{L,P}^G$. Taking smaller subsets picks out summands of this (note that the Mackey formula expresses restriction then induction as a sum over such double cosets).

The parabolic $P$ gives rise to an embedding of the root systems of $L$ into the root system of $G$ (I am being slightly sloppy here about how/when I'm choosing Borels... this can be made more precise in a number of different ways, hopefully all equivalent) . The Weyl group $W_L$ gets idetified with a parabolic subgroup $W_P$ of the Weyl group $W$ (similarly for $(Q,M)$). The Bruhat decomposition idetifies $Pbackslash G/Q$ with $W_P backslash W/W_Q$ (as sets).

By a minor abuse of terminology Levis $L$ and $M$ can be said to be conjugate if the root system of $L$ is conjugate to the root system of $M$ by an element of $W$. If we had chosen embeddings of $L$ and $M$ as subgroups of $G$, this is equivalent to them being conjugate as subgroups (independantly of the choice of parabolic). This is also equivalent to $W_P$ being conjugate to $W_Q$.

It follows from the Bruhat decomposition that $L$ and $M$ are conjugate if and only if there is a double coset in $Qbackslash G/P$ which is the image of a single Bruhat cell in $Pbackslash G$ and $G/Q$.

Let me make things more concrete for a second: suppose we fix a Borel $B$, and assume $P$ and $Q$ contain $B$. Then $P$ and $Q$ are conjugate if and only if they are equal. In that case $P$ itself is a double coset in $Pbackslash G/P$. which is already a Bruhat cell (i.e. a point). If $P$ and $Q$ are not conjugate, but $W_P$ and $W_Q$ are, then there is an element $ain W$ such that $W_PaW_Q = W_Pa = aW_Q$. This means that $PaQ = BaQ = PaB$.

Hence there is a canonical functor from $Rep(L)$ to $Rep(M)$. This functor is invertible (its inverse is the corresponding double coset in $Qbackslash G/P$). If we identify $L$ and $M$ compatibly with the identification of root systems then I claim this functor is the identity. Moreover, by its construction, this functor is a summand of $Res_{M,Q}^G Ind_{L,P}^G$. For a representation $V$ of $L=M$, the identification of $Ind_{L,P}^G$ with $Ind_{L,Q}^G$ is the adjoint of the inclusion $Vto Res_{L,P}^GInd_{L,Q}^GV$.

Remarks:
The parabolic induction and restriction functors can be thought of as pull-push of sheaves along the following correspondence:

$BL leftarrow BP rightarrow BG$.

The composition of the correspondences associated to $(P,L)$ and $(Q,M)$ is

$BL leftarrow BP times_{BG} BQ = Pbackslash G/Q rightarrow BM$.

For the anologue of these ideas in the setting of character sheaves, one should replace $Pbackslash G/Q$ with its loopspace, the corresponding relative Steinberg variety.

gr.group theory - What is the "permanence relation" really?

I have come across the words "permanence relation" in a 1969 paper by Keith Hannabuss The Dirac equation in de Sitter space. The only other similar google hit for this phrase appears in another paper of Hannabuss's with Alan Carey: Infinite dimensional groups and Riemann surface field theories.

As far as I can make out, this is the following. Suppose that $G$ is a group and $H<G$ a subgroup. (I'm being purposefully vague here about the kinds of groups: finite, Lie,...)

Let $operatorname{Res}: operatorname{Rep}(G) to operatorname{Rep}(H)$ denote the restriction functor from the category of complex $G$-modules to the category of complex $H$-modules, and let $operatorname{Ind}: operatorname{Rep}(H) to operatorname{Rep}(G)$ denote the induction functor going the other way.

Then the "permanence relation" seems to say that for every $G$-module $V$ and every $H$-module $W$,

$$operatorname{Ind}(W) otimes_{mathbb{C}} V cong operatorname{Ind}(W otimes_{mathbb{C}}operatorname{Res}(V))$$
as $G$-modules.

This strikes me as the $otimes$-version of the following isomorphism

$$operatorname{Hom}_H(W,operatorname{Res}(V)) cong operatorname{Hom}_G(operatorname{Ind}(W),V)$$

showing that $operatorname{Ind}$ and $operatorname{Res}$ are adjoint functors.

I'm not asking for a proof of the "permanence relation", which at least for finite group is not difficult, but more for a modern interpretation along the lines of the categorical interpretation of the above isomorphism of $operatorname{Hom}$'s. And perhaps also for a more modern name by which it might be known?

Thanks in advance.

Added

I just came across another name for this formula (based Tom's comment below): apparently it's also called a "push-pull" formula and there's even an earlier MO question about it! Although that question explicitly mentions the above "permanence relation" as one of the avatars of the "push-pull" formula, none of the answers address this particular avatar. Still, if people think that this question is a duplicate, I will not be offended if it is closed as such!

teaching - Looking for an introductory textbook on algebraic geometry for an undergraduate lecture course

I am now supposed to organize a tiny lecture course on algebraic geometry for undergraduate students who have an interest in this subject.

I wonder whether there are some basic algebraic geometry texts considering the level of undergraduate students who have not learnt commutative algebra or homological algebra; they just know linear algebra and basic abstract algebra.

I am looking for some textbooks which provide a lot of examples (more computations using linear algebra and calculus). Actually, I am also looking for some textbooks based on very basic mathematics but which talk a little bit about a modern view point.

Thanks in advance!

soft question - Your experience of Computer Science/Programming in Mathematics Education?

I taught my little sister calculus last summer by essentially giving her a mini numerical analysis course using Python. This enabled us to focus on the concepts of calculus, understanding definitions, and seeing how the major theorems all worked (on a discrete approximation level), all without much algebra (which is the major stumbling block for most students).

We coded a function grapher, a numerical differentiator, a numerical integrator , an diff Eq. solver. We also coded approximations to the exponential, log, and trig functions by viewing these functions as solutions to diff Eqs, and solved a lot of "real world" problems using these tools.

We bounded the error of our numerical integrator so that we could specify a desired degree of accuracy to our integral. This is obviously useful in any applied context (we need to know how accurate our approximations are), and it means she really recognized the importance of the formal definition of a limit.

Only after we had all the major concepts of calculus down did we start to play the symbolic manipulation games. This part of the course was less interesting, but we saw that it sped up our computations a lot (instead of having to do thousands of operations to approximate an integral, I can do maybe 10 to get the exact answer).

The experience was very interesting for me because I realized how much of calculus can be seen through the lens of Euler's method. You can really explain pretty much everything.

I am very interested in making a sequence of guided programming exercises which would teach calculus this way on the web. I started making some using Khan Academies open source material, but have not gotten very far. It will probably have to wait until the summer.

P.S. The net effect? I would say that she is weaker at churning out integrals than most students (I don't think we ever even talked about trig substitution, etc). However if you ask her what a derivative is she can tell you. If you ask her to explain how the fundamental theorem of calculus works, she can explain it to you. If you give her a novel physical problem she is very well equipped to think about breaking it into easy small subpieces, and using a limiting process to get a good approximation to a solution. In other words, I think that she has a much deeper understanding of calculus than a "standard" student, and because of this she will be able to apply calculus when it naturally arises in her life. She also learned how to program, which has independent value. We also had a lot of fun.

big picture - Idea of presheaf cohomology vs. sheaf cohomology

Let $X$ be a topological space and $U$ an open cover of $X$.

In this thread Angelo explained beautifully how presheaf cohomology (Cech cohomology) relates to sheaf cohomology:

The zeroth Cech cohomology functor $tilde H^0(U,-):Pre(X)to Ab$ from presheaves on $X$ to abelian groups is left exact and its right derived functors coincide with the cohomology $tilde H^n(U,-)$ of the chech complex. So one may interpret Cech cohomology as derived presheaf cohomology.

On the other hand the inclusion $i:Shv(X)to Pre(X)$ of sheaves on $X$ into presheaves is left exact and the diagram
[
begin{array}{rcl}
Shv(X)&xrightarrow{Gamma_X}&Ab\
isearrow&&nearrow tilde H^0(U,-)\
&Pre(X)&
end{array}
]
commutes. Let $Fin Shv(X)$ be a sheaf. The derived functors $H^n(X,F)$ of the left exact functor $Gamma_X$ are called sheaf cohomology. They are in general not equal to the derived functors $tilde H^n(U,-)$ (Cech cohomology). The relation between the two is the spectral sequence

$$
E_2^{p,q}=tilde H^p(U,H^q(-,F))Rightarrow H^{p+q}(X,F)
$$

induced by the Grothendieck spectral sequence.

• What is the general picture behind this?


• In this thread it is explained why the presheaf $H^q(-,F)$ in the spectral sequence sheafifies to zero for $qgeq 1$. How can one interpret this?


• For $X$ locally contractible and $F$ the sheaf of localy constant functions, sheaf cohomology equals singular cohomology and for a cover $U$ with two open sets the spectral sequence is just the Mayer Vietoris sequence. How does this fit into the general picture?

set theory - Pigeonhole Principle for infinite case

First, let me improve upon the countable counterexample of
Darij Grinberg by giving an uncountable counterexample Y.
Indeed, I shall give finite sets X_n and a subset Y of the product ΠX_n having size continuum (that is, as large as possible), such that any two distinct y, y' in Y
have only finitely many common values.

Let X_n have 2ⁿ elements, consisting
of the binary sequences of length n. Now, for each infinite
binary sequence s, let y_s be sequence in the
product ΠX_n whose n^th value is
s|n, the length n initial segment of s. Let Y consist of
all these y_s. Since there are continuum many s,
it follows that Y has size continuum.

Note that if s and t are distinct binary sequences, then eventually
the initial segments of s and t disagree. Thus, eventually,
the values of y_s and y_t are
different. Thus, y_s and y_t have only
finitely many common values. So Y is very large counterexample, as
desired.

A similar argument works still if the X_n grow
more slowly in size, as long as liminf|X_n| =
infinity. One simply spreads the construction out a bit
further, until the size of the X_i is large
enough to accommodate the same idea. That is, if the liminf
of the sizes of the X_n's is infinite, then one
can again make a counterexample set Y of size continuum.

In contrast, in the remaining case, there are no infinite
counterexamples. I claim that if infinitely many
X_n have size at most k and Y is a
subset of ΠX_n having k+1 many elements, then
there are distinct y,y' in Y having infinitely many common
values. To see this, suppose that Y has the property that
distinct y, y' in Y have only finitely many common values.
In this case, any two y, y' must eventually have different
values. So if Y has k+1 many elements, then eventually for
sufficiently large n, these k+1 many sequences in Y must be
taking on different values in every X_n. But
since unboundedly often there are only k possible values in
X_n, this is impossible.

In summary, the situation is as follows:

Theorem. Suppose that X_n is finite and
nonempty.

• If liminf |X_n| is infinite, then there is Y
  subset ΠX_n of size continuum, such that
  distinct y, y' in Y have only finitely many values in
  common.


• Otherwise, infinitely many X_n have size at most k for some k, and in this case, every Y subset
  ΠX_n of size k+1 has distinct y,y' in Y with infinitely
  many common values.

In particular, if the X_n become increasingly
large in size, then there are very bad counterexamples to the
question, and if the X_n are infinitely often
bounded in size, then there is a very strong positive answer to
the question.

ac.commutative algebra - Atiyah-MacDonald: exercise 5.29 - "local ring of a valuation ring"

Let B be the subring of K containing A. I am going to prove that B is the localization of A at a prime ideal $Psubset A$, which seems a reasonable interpretation of the statement that B is a local ring of A.

First B is a local ring [by Atiyah-MacDonald Prop 5.18 i)] ; let $M_B$ be its maximal ideal.
Similarly let $M_A$ be the maximal ideal of A.
Define $P=Acap M_B$. Then of course $Psubset M_A$ is prime and if we localize A at P, I claim that we get B:

a) If $pi in A-P$ then $pi notin M_B$ and so $pi$ is invertible in B. Hence for all $ a in A$ we have $a/ pi in B$.
This shows $A_P subset B$.

b) Now we see that B dominates $A_P$: this means we have an inclusion of local rings $A_P subset B$ and of their maximal ideals: $PA_P subset M_B$. But $A_P$ is a valuation ring of K because A is (This is the preceding exercise 28 : these guys know where they are heading!)
and valuations rings are maximal for the relation of domination (Exercise 27: ditto !).
Hence we have the claimed equality $B=A_P$.

riemann surfaces - How do you recover the structure of the upper half plane from its description as a coset space?

Edit: I should have put a short version of the answer in the beginning, so here is how the various structures are recovered. To get a smooth manifold structure on the quotient, you use the fact that $SL_2(mathbb{R})$ is a real Lie group and $SO_2(mathbb{R})$ is a closed subgroup. To get a hyperbolic structure, you use the fact that $SL_2(mathbb{R})$ is isomorphic to an orthogonal group of signature (n,1) for some n (giving a transitive action on hyperbolic n-space). To get a complex structure, you use the fact that $SL_2(mathbb{R})$ is isomorphic to an orthogonal group of signature (2,m) for some m (giving an action on a hermitian symmetric space).

As others have noted, you can get a bijection on points using the Iwasawa decomposition, and you can get a hyperbolic structure using the exceptional isomorphism $PSL_2(mathbb{R}) cong SO_{2,1}^+(mathbb{R})$. First, I'd like to clean up the Iwasawa treatment a bit. Any element of $SL_2(mathbb{R})$ can be uniquely decomposed as BK, where K is a rotation and B is upper triangular with positive diagonal. Any rotation K fixes i, so we should consider what elements B do. A bit of fiddling shows that $begin{pmatrix} sqrt{y} & x/sqrt{y} \ 0 & 1/sqrt{y} end{pmatrix} cdot i = x+iy$.

We can view the exceptional isomorphism in another way that makes the complex structure more apparent, by viewing the hyperbolic plane as the Grassmannian $O_{2,1}(mathbb{R})/(O_2(mathbb{R}) times O_1(mathbb{R}))$. From the standpoint of special relativity, this is the space of timelike lines through the origin in $mathbb{R}^{2,1}$. Taking a quotient of the total space of these lines (minus origin) by positive rescaling, we find that this space is isomorphic to the space of pairs of antipodal points of norm -1. In particular, we have an isomorphism of the Grassmannian with the quotient of the hyperboloid with two sheets (i.e., solutions of the equation $x^2 + y^2 - z^2 = -1$) by the antipodal automorphism.

One way to explain the origin of the complex structure is by the fact that all Grassmannians of the form $O(2,n)/(O(2) times O(n))$ are hermitian symmetric spaces, and the hyperbolic plane is just the case $n=1$. The 2 in $O(2)$ is essential, because the orthogonal group action is what yields the ninety degree rotation in the tangent space of any point, and this is what endows the quotient with an almost complex structure. If you want to see more about hermitian symmetric spaces than the Wikipedia blurb, I recommend looking in chapter 1 of Milne's introduction to Shimura varieties.

Finally, I'd like to point out Deligne's description of the upper half plane as a moduli space of structured elliptic curves. Points on H parametrize elliptic curves with an oriented basis of first homology (as mentioned a few times in our class). If you want to say it is a fine moduli space, you need a functor that it represents, and it is unfortunately a bit complicated. The functor takes as input the category of complex analytic spaces, and for any such space S, it gives the set of isomorphism classes of elliptic curves over S (i.e., diagrams $E underset{pi}{leftrightarrows} S$ of complex analytic spaces, where $pi$ is smooth and proper with one-dimensional genus one fibers and the leftward map is a section) equipped with an isomorphism $R^1pi_*underline{mathbb{Z}} cong underline{mathbb{Z} times mathbb{Z}}$ that induces the canonical identity $R^2pi_*underline{mathbb{Z}} cong underline{mathbb{Z}}$ on exterior squares. Here, the underscore indicates a constant sheaf. The functor also takes morphisms to "the evident diagrams". To be honest, I have never seen a complete proof that this functor is represented by the complex upper half plane, although it seems to be more a question of doing lots of writing than an honest theoretical problem. You can probably do it using the fact that H is a classifying space of polarized Hodge structures, as Kevin Buzzard mentioned in the comments.

nt.number theory - Neukirch's class field axiom and cohomology of units for unramified extension

This question may be too detailed but perhaps somebody knows the answer: Neukirch proofs in his algebraic number theory book in chapter IV, proposition 6.2, that his class field axiom implies that the tate cohomology groups H^n(G(L|K),U_L) for n=0,-1 vanish for finite unramified extensions L|K, where U_L is the group of units. He mentions in the proof that every element a in A_L can be written as a = epsilon * pi_K^m, where epsilon in U_L and pi_K is a prime element in A_K. Why does this work?
I absolutely understand this argument, when the image of the valuation just lies in ZZ! But how does this work for a valuation whose image is widehat{ZZ}? Unless A is not a profinite module, I don't know what pi_K^m is for some general m in widehat{ZZ}. Unfortunately this has to work in this generality for global class field theory.

(ZZ denotes the integers of course, sorry for my personal notation.)

dg.differential geometry - How do I make the conceptual transition from multivariable calculus to differential forms?

I have struggled with this question myself, and I couldn't find a perfectly satisfactory answer. In the end, I decided that the definition of a differential form is a rather strange compromise between geometric intuition and algebraic simplicity, and that it cannot be motivated by either of these by itself. Here, by geometric intuition I mean the idea that "differential forms are things that can be integrated" (as in Bachmann's notes), and by algebraic simplicity I mean the idea that they are linear.

The two parts of the definition that make perfect geometric sense are the d operator and the wedge product. The operator d is simply that operator for which Stokes' theorem holds, namely if you integrate d of a n-form over an n+1-dimensional manifold, you get the same thing as if you integrated the form over the n-dimensional boundary.

The wedge product is a bit harder to see geometrically, but it is in fact the proper analogy to the product measure. Here's how it works for one-forms. Suppose you have two one-forms a and b (on a vector space, for simplicity). Think of them as a way of measuring lengths, and suppose you want to measure area. Here's how you do it: pick a vector $vec v$ such that $a(vec v) neq 0$ but $b(vec v) = 0$ and a vector $vec w$ s.t. $a(vec w) = 0$ but $b(vec w) neq 0$. Declare the area of the parallelogram determined by $vec v$ and $vec w$ to be $a(vec v) cdot b(vec w)$. By linearity, this will determine area of any parallelogram. So, we get a two-form, which is in fact precisely $a wedge b$.

---

Now, the part that makes no sense to me geometrically is why the hell differential forms have to be linear. This implies all kinds of things that seem counter-intuitive to me; for example there is always a direction in which a one-form is zero, and so for any one-form you can draw a curve whose "length" with respect to the form is zero. More generally, when I was learning about forms, I was used to measures as those things which we integrate, and I still see no geometric reason as to why measures (and, in particular, areas) are not forms.

However, this does make perfect sense algebraically: we like linear forms, they are simple. For example (according to Bachmann), their linearity is the thing that allows the differential operator d to be defined in such a way that Stokes' theorem holds. Ultimately, however, I think the justification for this are all the short and sweet formulas (e.g. Cartan's formula) that make all kinds of calculations easier, and all depend on this linearity. Also, the crucial magical fact that d-s, wedges, and inner products of differential forms all remain differential forms needs this linearity.

Of course, if we want them to be linear, they will be also signed, and so measures will not be differential forms. To me, this seems as a small sacrifice of geometry for the sake of algebra. Still, I don't believe it's possible to motivate differential forms by algebra alone. In particular, the only way I could explain to myself why take the "Alt" of a product of forms in the definition of the wedge product is the geometric explanation above.

So, I think the motivation and power behind differential forms is that, without wholly belonging to either the algebraic or geometric worlds, they serve as a nice bridge in between. One thing that made me happier about all this is that, once you accept their definition as a given and get used to it, most of the proofs (again, I'm thinking of Cartan's formula) can be understood with the geometric intuition.

Needless to say, if anybody can improve on any of the above, I'll be very grateful to them.

P.S. For the sake of completeness: I think that "inner products" make perfect algebraic sense, but are easy to see geometrically as well.

Function Field of projective space

The function field of $V$ is defined as the field of fractions of $K[X]/I(V)$ for affine varieties $V$. In the case of projective varieties, Silverman chooses a Zariski-dense affine open subset $V$ of the variety and defines the function field of the variety as the function field of the subset $V$. Of course, one can prove it is independent of the choice of $V$. When the variety is $mathbb{P}^n$, choose $V = mathbb{A}^n$ and so $I(V)={ 0 }$, so $K(mathbb{P}^n) = K(V) = K[X]/{ 0 } = K[X]$, where $X$ is shorthand for $X_1,ldots,X_n$. Finally to get an isomorphism of the subfield of $K(X_0,ldots,X_n)$ you described with the field I just described, just set $X_0=1$.

gr.group theory - to test equivalence of representations under automorphism

I assume that $phi$ is an automorphism of $G.$ Note that if $phi$ is inner then trivially $rho$ and $rhocircphi$ are equivalent, thus the answer depends only on the image of $phi$ in the outer automorphism group $Out(G).$

If $G$ is a finite group (or, more generally, compact group) and representations are finite-dimensional, so that they are determined up to isomorphism by their characters, then this problem admits a complete theoretical solution using the character theory. The automorphism group $Aut(G)$ acts on the set ${C_i}$ of the conjugacy classes of $G$, this action factors through the action of $Out(G),$ and

$$chi_{rhocircphi}(C)=chi_{rho}(phi(C)),qquad (*)$$

where $chi_rho$ is the character of $rho$ and $C$ is any conjugacy class. Since representations are determined by their characters,

$$rhocircphisimeqsigma iff chi_{rhocircphi}=chi_sigma,$$

which can be tested using $(*).$ Of course, applying this method in practice requires good knowledge of the character table of $G$ and the outer automorphism group $Out(G).$

Given a number field $K$, when is its Hilbert class field an abelian extension of $mathbb{Q}$?

I happened to come across this question again today. In some cases at least, the Hilbert class field $H$ of an abelian extension $K$ of $mathbf{Q}$ will have to be abelian over $mathbf{Q}$ for purely algebraic reasons.

Let $F$ be any field, $K|F$ an abelian extension of group $G=mathrm{Gal}(K|F)$ and containing a primitive $n$-th root of unity for some $n>1$, $omega:Gto(mathbf{Z}/nmathbf{Z})^times$ the cyclotomic character giving the action of $G$ on $mu_n$, and $H|K$ an abelian extension of exponent dividing $n$. Then $H=K(root nof D)$ for some subgroup $Dsubset K^times/K^{times n}$, by Kummer theory. It can be checked that $H|F$ is galoisian if and only if $D$ is $G$-stable. When such is the case, the conjugation action of $G$ on $mathrm{Gal}(H|K)$ coming from the short exact sequence
$$
1tomathrm{Gal}(H|K)tomathrm{Gal}(H|F)to Gto1
$$
is trivial if and only if $G$ acts on $D$ via $omega$. In this situation ($H=K(root nof D)$ for some subgroup $Dsubset(K^times/K^{times n})(omega)$), a sufficient condition for $H$ to be abelian over $F$, is that the order of $G$ be prime to $n$, because then $mathrm{Gal}(H|F)=mathrm{Gal}(H|K)timesmathrm{Gal}(K|F)$.

I'm sure this situation can be realised when $F=mathbf{Q}$, for example when the finite abelian extension $K$ has odd degree $[K:mathbf{Q}]$, $n=2$, the class group of $K$ has order ($1$ or) $2$, and $H$ is the Hilbert class field of $K$. In this case the extension $H|mathbf{Q}$ will be necessarily abelian.

ag.algebraic geometry - Semiclassical explanation of "Structured" spaces

We have our general notions of manifolds, schemes, et cetera, and other geometric "spaces", and we realize that a lot of these look like topological spaces with structure sheaves i.e. structured spaces.

In part 5 of Lurie's DAG, he describes this notion in terms of (infinity,1)-topoi. However, I don't see myself being able to read DAG any time soon (I'm still going through HTT), so I have a somewhat easier question:

If we consider the same topic in terms of the semiclassical constructions, that is, algebraic stacks and orbifolds, or even schemes and manifolds, can we describe precisely what our "structured spaces" should be to be useful? Why is it standard to talk about the sheaves on a scheme where we talk about bundles on a manifold? Aren't these concepts the same thing? How much of what we talk about in differential geometry and algebraic geometry can be jointly generalized to structured spaces?

If this question is too vague, then just tell me where I can find out.

Edit: To correct my previous vagueness, as Pete pointed out, we want local rings, or their appropriate counterparts for stacks.

Edit 2: To clarify, I'm looking for either a book that's a dumbed-down version of DAG book 5, or someone to dumb down the idea from (infinity,1)-categories to plain categories or sets.

gr.group theory - Is there a way to see a topological group as the "Cayley graph" of its "infinitesimal generators"?

At the time of writing, the most recent blog post over at What's new by Terrence Tao is Cayley graphs and the geometry of groups, and that (excellent, as with most of Tao's writing) post most immediately inspired this question. Also, a disclaimer: Cayley graphs, and, indeed, abstract group theory generally, are not my area of expertise, so feel free to explain how my question is overly naive and/or needs revision.

It is a classical result that a connected topological group is generated by any open neighborhood of its identity element. (Proof: the subgroup generated by the open neighborhood is a union of opens, and hence open; but then so are all its cosets; so this subgroup is both open and closed; hence it is everything if the group is connected as a topological space.) So I am tempted to take some topological group $G$, and some very small neighborhood $S$ of the identity $e$, and construct the corresponding Cayley graph. My intuition says that as $S$ gets smaller and smaller, the Cayley graph better and better approximates the topological space $G$. Notice also that arbitrary small open neighborhoods $Sni e$ know everything about the topology of $G$, because $G$ is homogeneous.

I don't know how to define a "formal neighborhood" of a topological space, unless it is actually a manifold or algebraic space or .... So maybe I should restrict my attention to Lie or Algebraic groups for this question. But anyway:

Is there a way to define the "infinitesimal generators" or "formal neighborhood" for a topological group in such a way that the corresponding "Cayley graph" is the group as a topological space (Edit: which of course doesn't make any sense; see the comments. I mean something like "so that the geometry/topology of the group comes immediately from the graph)? If not in this generality, does it at least work when the group is Lie? Algebraic? Or other regularity conditions on the topology?

co.combinatorics - Extremal question on matrices

The following looks too simple, so perhaps there's a mistake, but here goes.

Let $m$ be the smallest among all row sums and column sums. If $mgeq n/2$, we are done.

Otherwise, $m=cn$ with $clt 1/2$. Suppose it is a column which has sum $m$. This column has at least $n-m$ zeroes, and each of the corresponding rows has sum $geq n-m$. The remaining $m$ rows each has sum $geq m$.

In total we have a sum of at least $(n-m)^2+m^2 = ((1-c)^2+c^2)n^2$. Finally, note that $(1-c)^2+c^2gt 1/2$ when $clt 1/2$.

So this gives a lower bound of $n^2/2$, and equality requires that any row and any column sums to exactly $n/2$, so the matrix is a sum of $n/2$ permutation matrices by König's Theorem.

Now what about the case when $n$ is odd?

Edit: Since the sum is an integer, the lower bound $n^2/2$ actually gives $(n^2+1)/2$, which can be attained by for example taking the direct sum of an $mtimes m$ matrix of $1$s with an $(n-m)times (n-m)$ matrix of $1$, where $m=(n-1)/2$. When $n$ is odd, this is the only extremal example up to column and row permutations. Here is a proof.

Let $m$ now, as originally, denote the minimum over all row and column sums. If $mgeq (n+1)/2$, then the total sum is too large: at least $nmgeq n(n+1)/2$. Therefore, $mleq(n-1)/2$, and the $(n-m)^2+m^2$ lower bound now gives a total sum of at least $(n-n(n-1)/2)^2+((n-1)/2)^2 = (n^2+1)/2$ (using the fact that $(1-c)^2+c^2$ is decreasing when $clt 1/2$).
So up to now we have only rederived the lower bound for $n$ odd.

However, if equality now holds, we get that $m=(n-1)/2$, that each row adds up to either $m$ ($m$ times) or $n-m$ ($n-m$ times), and that in a column that adds up to $m$, there are exactly $n-m$ $0$s, so all entries are $0$ or $1$ (and similar statements with columns and rows interchanged). By permuting the rows and columns we may assume that the first $m$ rows [columns] each add up to $m$.There can't be a $0$ in the upper left $mtimes m$ submatrix, since then the sum of the row and column containing the $0$ adds up to only $2mlt n$. We have found a direct sum of an $mtimes m$ and an $(n-m)times(n-m)$ all $1$ matrix.

ag.algebraic geometry - generators of the ideal of an unipotent-generated algebraic group

Given any affine algebraic group $G$ over an algebraically closed field $mathbb{F}$ of characteristic $0$ with a faithfull representation in $GL_n(mathbb{F})$ . If one knows the generators of the corresponding ideal, what can be said about the generators of $G^u$. Here $G^u$ shall denote the group generated by all unipotent elements of $G$. (Unlike the case where $G$ is irreducible and solvable, this group is not necessarily unipotent).

I am particular interested in bounds on the degrees of the generators; also any reference, which deals with unipotent generated groups is welcome.

gr.group theory - group action and orbit space

I don't really see why there should be general results. We can take W to be a vector space over a finite field, and then you are asking about equivalence of linear representations of G on W. The data you will give me is about the stabilisers H(w) of the w in W, and as I understand it there will be just this. But I think there are many examples where W will be very homogeneous (taking out 0). And there will be cases, for example, where there will be inequivalent linear representations of G that are related by outer automorphisms of G. If you tell me you can detect enough about the representations to determine their equivalence by some general method, without further hypotheses, I shall need convincing.

rt.representation theory - (When) does Schur's lemma break?

The idea behind Schur's Lemma is the following. The endomorphism ring of any simple $R$-module is a division ring. On the other hand, a finite dimensional division algebra over an algebraically closed field $k$ must be equal to $k$ (this is because any element generates a finite dimensional subfield over $k$, which must be equal to $k$).

Thus, when $R$ is an algebra over an algebraically closed field $k$, the endomorphism ring of a finite dimensional simple module is a finite dimensional division algebra over $k$ and hence is equal to $k$.

On the other hand, let $D$ be any division algebra over a field $k$, which we no longer assume to be algebraically closed. Then $D_D$ is a simple module, and $text{End}_D(D)cong D$. This allows us to break Schur's Lemma two different ways. If $D$ is infinite-dimensional and $k$ algebraically closed, the endomorphism ring $text{End}_D(D)$ will also be infinite dimensional over $k$, hence not isomorphic to $k$. We can easily come up with such $D$, even commutative examples. For instance, $k(x)$ will be an infinite dimensional division algebra over $k$. On the other hand, if $k$ is not algebraically closed, we can take $D$ to be a finite field extension, and we get a $text{End}_D(D)cong D$ not isomorphic to $k$.

nt.number theory - An inequality relating the factorial to the primorial.

Let [a,b] = {k integer | a < k <= b}. Further let

• Comp[a,b] = product_{c in [a,b]} c composite;
  


• Fact[a,b] = product_{k in [a,b]} k integer;
  


• Prim[a,b] = product_{p in [a,b]} p prime.

Question: For n > 2 and n not in {10,15,27,39} is it true that

$$ text{Comp}[{leftlfloor n /2 rightrfloor}, n] < text{Fact}[1, {leftlfloor n /2 rightrfloor}] text{Prim}[{leftlfloor n /2 rightrfloor}, n] ? $$

Update: The state of affairs: Gjergji Zaimi showed that for large enough n the inequality is true. In my answer I affirm that the inequality is true in the range 40 <= n <= 10^5. It remains open whether 10^5 is 'large enough' in the sense of Gjergji's analysis.

ac.commutative algebra - Selforthogonal modules over Artinian Gorenstein Rings.

This would be a very strong version of the Auslander-Reiten Conjecture (see here, for example) in the Gorenstein case. The Conjecture is still open, though many partial results are known.

By the way, this paper (ScienceDirect link, may not be visible to everyone) claims a proof of the Conjecture in the Gorenstein case, which would give an affirmative answer to your question, but I --- and several other people I've talked to --- believe there is a gap in the proof. Their assumption is that $mathrm{Ext}_R^{i}(M,M)=0$ for $i =1,2$. The questionable step is at the top of page 2163, the second line, where they say "therefore ... is exact".

lo.logic - Ideals of statements?

The following is a somewhat vague question concerning logic, but with ideas from algebraic geometry (see in particular the example at the end). The vagueness is in the notion of "language".

Let $A$ be a set and fix some language in which to write propositions which assign a value of true or false to each element of A. Let $R$ be the set of such propositions about elements of $A$, and suppose that $R$ contains "True" and "False" and is closed under "and" ($wedge$) and "or" ($vee$).

Now let $Vsubseteq A$ be a subset and consider the set $I(V)subseteq R$ such that $rin I(V)$ iff $r$ holds of every element $vin V$. This set $I(V)$ has the following properties:

1. "True" is in $I(V)$,


2. If $i$ and $j$ are in $I(V)$ then $iwedge j$ is in $I(V)$, and


3. If $i$ is in $I(V)$ and $rin R$ then $rvee i$ is in $I(V)$.

Thus $I(V)$ satisfies the axioms of an "ideal" in the "ring" $R$ if we take the following "strange correspondence" between statements and algebraic operations: $Tmapsto 0$, $Fmapsto 1$, $wedgemapsto +$ and $veemapsto times$. Note that in fact $R$ is a commutative "Rig" (ring without negatives) under this "strange correspondence." The correspondence is "strange" because we usually think of "or" as $+$, "and" as $times$, "true" as $1$, and "false" as $0$. But we can find intuition for this correspondence via Example 2 below.

Suppose we define an ideal in $R$ to be a subset $Isubseteq R$ satisfying conditions 1,2,3. Given an ideal $I$ we can consider the set $Z(I)subseteq A$ of all elements $ain A$ such that $i$ holds of $a$ for each $iin I$. Call such subsets "closed".

Observation 1: There is an (order-reversing) correspondence between the ideals of $R$ and the closed subsets of $A$.

Example 2: Suppose we take the language of commutative rings. Say $A$ is the set ${mathbb R}^n$ and $R$ is the set of statements of the form $f(x_1,ldots,x_n)=0$ where $f$ is a polynomial with real coefficients. The set of such statements forms a ring, by operating on the polynomials; that is $Rcong {mathbb R}[x_1,ldots,x_n]$.

Given a subset $Vsubseteq A$ we can consider those equations that are true of all points in $V$. Such a subset will satisfy conditions 1,2,3 above (where "True" is 0=0). We see that the "strange correspondence" discussed above does make sense: if $f=0$ and $g=0$ hold of every point in $V$ then so does $f+g=0$; for any equation $r=0$ in $R$, if $f=0$ holds of every point in $V$ then so does $rf=0$. The empty subset of $A$ is satisfied by $1=0$ (or "false"). In fact, Observation 1 is the basic observation of algebraic geometry in this context.

Question 3: Has anyone looked at this correspondence? Can it be made more rigorous? Can algebro-geometric notions (like schemes) be applied to other "languages" in an interesting way?

ap.analysis of pdes - Solitary waves and their symmetries

This is probably a very naive question from a field that I don't have much background from, but a combination of curiosity and the fact that conceptual questions get very good answers here on MO seemed enough motivation to ask it.

Solitons are very interesting objects for a number of special properties they have, such as being "particle like", being stable and conserving their geometric features. Some of these properties are related to symmetries related to the notion of solitons, symmetries whose presence is mysterious to me.

My question is, therefore, what is a conceptually satisfying explanation of the non-obvious symmetries of solitons? Where do they come from and/or what causes them? I could not even perform a (fruitful) basic search since I don't know even the key-words necessary for it.

ag.algebraic geometry - generators of the ideal of an unipotent-generated algebraic group

Given any affine algebraic group $G$ over an algebraically closed field $mathbb{F}$ of characteristic $0$ with a faithfull representation in $GL_n(mathbb{F})$ . If one knows the generators of the corresponding ideal, what can be said about the generators of $G^u$. Here $G^u$ shall denote the group generated by all unipotent elements of $G$. (Unlike the case where $G$ is irreducible and solvable, this group is not necessarily unipotent).

I am particular interested in bounds on the degrees of the generators; also any reference, which deals with unipotent generated groups is welcome.

set theory - Products of Baire spaces

See:

Cohen, Paul E.
Products of Baire spaces.
Proc. Amer. Math. Soc. 55 (1976), no. 1, 119--124.

$ $

MathSciNet review by Douglas Censer: A topological space is said to be Baire if any countable intersection of its dense open sets is dense. Assuming the continuum hypothesis (CH), J. C. Oxtoby [Fund. Math. 49 (1960/61), 157--166; MR0140638 (25 #4055); errata, MR 26, p. 1543] constructed a Baire space whose square is not Baire. The author shows that the assumption of CH is unnecessary here. The spaces considered in this paper are partially ordered $(P,leq)$ with topology generated by the initial segments. The construction of the desired Baire space with non-Baire product is based on the study of $P$ as a set of forcing conditions, as outlined by R. M. Solovay [Ann. of Math. 92 (1970), 1--56; MR0265151 MR0265151 (42 #64)].

Note that googling "products of Baire spaces" returns Cohen's article as the second hit. (The first hit is this question!)

For a positive result, see

Zsilinszky, László
Products of Baire spaces revisited.
Fund. Math. 183 (2004), no. 2, 115--121.

Excerpted from the MathSciNet review by Paul Bankston: Without extra assumptions, the product of two Baire spaces need not be Baire [see, e.g., J. C. Oxtoby, Fund. Math. 49 (1960/1961), 157--166; MR0140638 (25 #4055); P. E. Cohen, Proc. Amer. Math. Soc. 55 (1976), no. 1, 119--124; MR0401480 (53 #5307)]. This brings us to the notion of a $pi$-base; i.e., a collection of open sets such that every nonempty open set in the space contains a member of the collection. A $pi$-base each of whose members contains only countably many members of the $pi$-base is called countable-in-itself.

Oxtoby's theorem, from his 1961 paper, states that any Tikhonov (resp., finite) product of Baire spaces with countable (resp., countable-in-itself) $pi$-bases is a Baire space. The main result of the present paper is a significant strengthening of this; in particular it implies that arbitrary Tikhonov products of Baire spaces with countable-in-itself $pi$-bases are Baire spaces.

A space $X$ is called universally Kuratowski-Ulam (uK-U for short, first considered in [C. Kuratowski and S. Ulam, Fund. Math. 19 (1932), 247--251; Zbl 0005.18301]) if whenever $Y$ is a space and $E$ is a meager subset of $Xtimes Y$, the set $ Y setminus {yin Y: {xin X: (x,y)in E} text{is meager in} X} $ is meager in $Y$. The author now defines a space $X$ to be almost locally uK-U if the set ${xin X: x text{has an open uK-U neighborhood} }$ is dense in $X$.

After showing that the property of being almost locally uK-U is a proper generalization of having a countable-in-itself $pi$-base, the author proves his main theorem: only a Tikhonov (or countable box) product of Baire spaces that are almost locally uK-U is a Baire space.

The proof for the box product case is a variant of that for the Tikhonov case, and partially answers a question raised in [W. G. Fleissner, in General topology and its relations to modern analysis and algebra, IV (Proc. Fourth Prague Topological Sympos., Prague, 1976), Part B, 125--126, Soc. Czechoslovak Mathematicians and Physicists, Prague, 1977; MR0464181 (57 #4116)].

spherical geometry - Grid with nice mathematical properties

Unfortunately, the sphere is not a "developable surface". This fact has annoyed map-makers for more than a millennium.

I find your focus on "cells" fascinating.
Most people seem fixated on trying to get points on the globe to correspond with points on a flat image, and don't seem concerned about dividing it up into areas.
The simplest way to convert (lat,long) coordinates to standardized areas is the "Natural Area Code", but it has the same problems near the poles as latitude and longitude.

Your "too many close grid cells" and "Distance between a cell and a point" criteria reminds me of the "Thomson problem".
I suspect you're trying to rule-out map projections like the Gall–Peters projection that, while they do have nice "equal area" properties, end up having a hundred little squares at the top and bottom of the on the map projected to a hundred long, narrow pie-slices that all touch a pole of the globe.

Perhaps you could pick one of the known solutions to the "Thomson problem" to build a nice grid. Most of those solutions look similar to a geodesic sphere -- but there are a few exceptions.

Perhaps the most famous application for "almost equal" patches is the Cosmic Background Explorer (COBE), which has inspired several mappings:

The COBE "bins" are, as far as I can tell, a synonym for your "cells".

Are those COBE-inspired mappings adequate for you?

at.algebraic topology - understanding Steenrod squares

The Steenrod square is an example of a cohomology operation. Cohomology operations are natural transformations from the cohomology functor to itself. There are a few different types, but the most general is an unstable cohomology operation. This is simply a natural transformation from $E^k(-)$ to $E^l(-)$ for some fixed $k$ and $l$. Here, one regards the graded cohomology functors as a family of set-valued functors so the functions induced by these unstable operations do not necessarily respect any of the structure of $E^k(X)$.

Some do, however. In particular, there are additive cohomology operations. These are unstable operations which are homomorphisms of abelian groups.

In particular, for any multiplicative cohomology theory (in particular, ordinary cohomology or ordinary cohomology with $mathbb{Z}/2mathbb{Z}$ coefficients) there are the power operations: $x to x^k$. These are additive if the coefficient ring has the right characteristic. In particular, squaring is additive in $mathbb{Z}/2mathbb{Z}$ cohomology.

Given an unstable cohomology operation $r: E^k(-) to E^l(-)$ there is a way to manufacture a new operation $Omega r: tilde{E}^{k-1} to tilde{E}^{l-1}(-)$ using the suspension isomorphism (where the tilde denotes that these are reduced groups):

$E^{k-1}(X) cong E^k(Sigma X) to E^l(Sigma X) cong E^{l-1}(X)$

This is quite straightforward and is a cheap way of producing more operations. When applied to the power operations it produces almost nothing since the ring structure on the cohomology of a suspension is trivial: apart from the inclusion of the coefficient ring all products are zero.

What is an interesting question is whether or not this looping can be reversed. Namely, if $r$ is an unstable operation, when is there another operation $s$ such that $Omega s = r$? And how many such are there? Most interesting is the question of when there is an infinite chain of operations, $(r_k)$ such that $Omega r_k = r_{k-1}$. When this happens, we say that $r$ comes from a stable operation (there is a slight ambiguity here as to when the sequence $(r_k)$ is a stable operation or merely comes from a stable operation).

One necessary condition is that $r$ be additive. This is not, in general, sufficient. For example, the Adams operations in $K$-theory are additive but all but two are not stable.

However, for ordinary cohomology with coefficients in a field, additive is sufficient for an operation to come from a stable operation. Moreover, there is a unique sequence for each additive operation. This means that the squaring operation in $mathbb{Z}/2mathbb{Z}$ cohomology has a sequence of "higher" operations which loop down to squaring. These are the Steenrod squares.

The sequence stops with the actual squaring (rather, becomes zero after that point) because, as remarked above, the power operations loop to zero.

One important feature of these operations is that they give necessary conditions for a spectrum to be a suspension spectrum of a space. If a spectrum is such a suspension spectrum then it's $mathbb{Z}/2mathbb{Z}$-cohomology must be a ring. That's not enough, however, it must also have the property that, in the right dimensions, the Steenrod operations act by squaring. (Of course, this is necessary but not sufficient.)