User qiaochu yuan - MathOverflow

Answer by Qiaochu Yuan for objects which can't be defined without making choices but which end up independent of the choice

2013-05-20T22:04:39Z

The simple groups appearing in a composition series of a finite group are independent of the choice of composition series by the Jordan–Hölder theorem, but I'm not aware of a way to define these groups that doesn't involve a choice of composition series.

Answer by Qiaochu Yuan for Is there any proof that you feel you do not "understand"?

2013-05-17T04:38:23Z

The first proof of Tychonoff's theorem I learned, from the Alexander subbase theorem, was completely mysterious to me. I didn't understand it at all. In particular I didn't really understand what the precise role of the axiom of choice was.

Later I learned that there is a much more intuitive proof using ultrafilters or, equivalently, nets. This proof also makes clear the role of the axiom of choice. You want to capture the following intuition: if $X_i$ is a collection of compact spaces and $a : \mathbb{N} \to \prod X_i$ is a sequence, then it should suffice to pick a limit point in each of the projections of $a$ to a sequence in each $X_i$ to show that $a$ itself has a limit point. Unfortunately, sequence convergence doesn't capture the topology of spaces in general, but net convergence and ultrafilter convergence both do, and the above proof works more or less verbatim with "sequence" replaced by either "net" or "ultrafilter."

The axiom of choice enters twice: first a weak version enters in setting up the basic theory of nets or ultrafilters (you need the ultrafilter lemma either way I think), and second the full version enters when picking a limit point in each $X_i$.

This proof also shows that if you only want to prove that a product of compact Hausdorff spaces is compact Hausdorff (often enough for applications), you only need the ultrafilter lemma: the second use of choice doesn't enter into the picture because limit points of ultrafilters are unique if the $X_i$ are Hausdorff! (I assume a similar statement is true for nets but I'm not sure.)

Answer by Qiaochu Yuan for Is it true that Nature promotes products?

2013-05-14T23:06:18Z

You need to distinguish between "coproduct" and "comultiplication." The categorical coproduct is just a generalization of addition and is intuitive in many contexts.

Comultiplications are more interesting. Actually it turns out that many familiar mathematical objects are canonically equipped with comultiplications. In fact, in any category $C$ with finite products every object $c$ has a canonical comultiplication given by the diagonal map $\Delta : c \to c \times c$. On sets this is the diagonal map $x \mapsto (x, x)$. In other words, in such a category $C$ every object is canonically a coalgebra. Usually this structure is invisible, but coalgebras are preserved by monoidal functors, so for example the free vector space on a set is canonically a coalgebra in vector spaces. Usually this structure is also invisible, but it appears for example in the Hopf algebra structure on group rings...

In particular, every topological space is canonically a coalgebra. Now, homology (over a field) is a covariant monoidal functor, so it sends coalgebras to coalgebras. But cohomology is a contravariant monoidal functor, so...

Another source of comultiplications is combinatorics. Where multiplications are intuitively like "building things up," comultiplications are intuitively like "breaking things down." And this allows you to define many natural coalgebras by breaking down combinatorial structures into parts. For example, $R[x]$ has a natural $R$-linear comultiplication given by

$$x^n \mapsto \sum_k x^k \otimes x^{n-k}$$

and this reflects the process of breaking apart a string of length $n$ into two strings of length $k$ and $n-k$. The dual of this coalgebra is the algebra of ordinary generating functions over $R$. Similarly, there is another comultiplication given by

$$x^n \mapsto \sum_k {n \choose k} x^k \otimes x^{n-k}$$

and this reflects the process of breaking apart a set of size $n$ into two subsets of size $k$ and $n-k$. The dual of this coalgebra is the algebra of exponential generating functions over $R$.

In the same spirit, Rota noticed that the incidence algebra of a poset is naturally regarded as the dual of an incidence coalgebra, namely the free vector space on intervals $[a, b]$ in the poset with comultiplication given by

$$[a, b] \mapsto \sum_{a \le c \le b} [a, c] \otimes [c, b]$$

and this reflects the process of breaking apart an interval into two subintervals.

Yet another source of comultiplications comes from objects in a category $C$ which represent a (covariant) functor to the category of monoids. For example, the fundamental group functor $\text{hTop}_{\ast} \to \text{Grp}$ is represented by the object $S^1$ in the (pointed) homotopy category, and this is because $S^1$ naturally has a cogroup structure. Similarly, the multiplicative group functor $\text{CRing} \to \text{Grp}$ is represented by the object $\mathbb{Z}[x, x^{-1}]$, which also naturally has a cogroup structure (in fact a commutative Hopf algebra is precisely a cogroup object in $\text{CRing}$, or equivalently is precisely the ring of functions on an affine group scheme).

Comultiplications only seem unfamiliar because they were historically not pointed out, but actually they are all over the place. See also What is a coalgebra intuitively?

Is a "non-analytic" proof of Dirichlet's theorem on primes known or possible?

2010-03-01T02:02:18Z

It is well-known that one can prove certain special cases of Dirichlet's theorem by exhibiting an integer polynomial $p(x)$ with the properties that the prime divisors of $\{ p(n) | n \in \mathbb{Z} \}$ must lie in certain arithmetic progressions, with a finite number of exceptions. This is because any nonconstant polynomial must have infinitely many distinct prime divisors, which one can prove in a manner imitating Euclid's proof of the infinitude of the primes. For example, taking $p(x) = \Phi_n(x)$, we can prove Dirichlet's theorem for primes congruent to $1 \bmod n$. It is known (see, for example, this paper of K. Conrad) that this is possible precisely for the primes congruent to $a \bmod n$ where $a^2 \equiv 1 \bmod n$.

However, the result about polynomials having infinitely many prime divisors has the following generalization: any sequence $a_n$ of integers which is eventually monotonically increasing and which grows slower than $O(2^{\sqrt[k]{n}})$ for every positive integer $k$ has infinitely many distinct prime divisors. In particular, any sequence of polynomial growth (not necessarily a polynomial itself) has this property.

Question 1: Given an arithmetic progression $a \bmod n, (a, n) = 1$ such that $a^2 \not \equiv 1 \bmod n$, is it ever still possible to efficiently construct a monotonically increasing sequence of positive integers satisfying the above growth condition such that, with finitely many exceptions, the prime divisors of any element of the sequence are congruent to $a \bmod n$? ("Efficiently" rules out answers like "the positive integers divisible by primes congruent to $a \bmod n$," since I do not think it is possible to write down this sequence efficiently. On the other hand, evaluating a polynomial is very efficient.) The idea is that such a sequence immediately gives a proof of Dirichlet's theorem for primes congruent to $a \bmod n$ generalizing the Euclid-style proofs.

Question 2: If the above is not possible, are there any known techniques for proving Dirichlet's theorem or at least some of the special cases not covered above without resorting to the usual analytic machinery? For example, Selberg published an "elementary" proof in 1949, but it relies on the "elementary" proof of the prime number theorem, which to me is "finitary analytic machinery." What is the absolute minimum amount of analysis necessary to produce a proof? (Edit: In response to a suggestion in the comments, one way to describe the kind of answer I'm looking for is that it would generalize to a proof of Chebotarev's density theorem that shows very clearly where the distinction between the number field and function field cases is; aside from some "essential" analytic argument there should be no difference between the two.)

This question is inspired at least in part by the following observation: Dirichlet's theorem is equivalent to the seemingly weaker statement that for every progression $a \bmod n, (a, n) = 1$ there exists at least one prime congruent to $a \bmod n$. The reason is that if there exists some such prime $a_1$, then letting $n_1$ be the smallest multiple of $n$ greater than $a_1$, there exists a prime congruent to $a_1 + n \bmod n_1$, and so forth.

Does this kind of endofunctor ever have an initial algebra?

2013-04-23T06:04:30Z

Let $C$ be a topos with subobject classifier $\Omega$. Let $F$ be the endofunctor $x \mapsto \Omega^{\Omega^x}$ on $C$. Does there exist $C$ such that $F$ has an initial algebra? What if $\Omega$ is replaced with the coproduct $2 = 1 \sqcup 1$ of two copies of the terminal object? (What if it is replaced with any object that is not the terminal object?)

The motivation for this question is a somewhat long story, but if someone wants I can edit it in.

Note that if $C = \text{Set}$ then this is impossible by Cantor's theorem (and Lambek's theorem). I'm worried that the Lawvere fixed point theorem can shoot down this question as well.

Answer by Qiaochu Yuan for Tannaka duality for C*-algebras?

2013-04-21T20:06:54Z

This isn't an answer but a long comment. Tannaka-Krein duality will mislead you about how hard you should expect this result to be. "Tannaka-Krein duality for rings" is actually very easy and looks like this.

Theorem: Let $R$ be a ring. Then $R$ is isomorphic to the endomorphism ring of the forgetful functor $\text{Mod-}R \to \text{Ab}$. (Recall that the category of functors from a category into an $\text{Ab}$-enriched category is $\text{Ab}$-enriched, so endomorphism monoids are rings.)

Proof. This functor is represented by the right $R$-module $R_R$, so its endomorphism ring is the endomorphism ring of $R_R$ by the Yoneda lemma. By a second application of the Yoneda lemma (!), the endomorphism ring of $R_R$ is $R$. $\Box$

(And of course if you forget the forgetful functor then you cannot recover $R$ at all, only its Morita equivalence class.)

"Set-theoretic Tannaka-Krein duality for monoids" is also very easy and says that a monoid $M$ is isomorphic to the endomorphism monoid of the forgetful functor $\text{Set-}M \to \text{Set}$; the proof is identical. Tannaka-Krein duality itself is hard because we are considering linear representations of groups, which a priori should only let us at best recover the group algebra; we need more structure (e.g. the tensor product) to recover the group itself.

Answer by Qiaochu Yuan for Age of Stochasticity?

2013-04-18T08:12:56Z

Here is a result that gives the flavor of the kind of thing along these lines I hope to see in the future. Recall Tarski's undefinability of truth: under suitable assumptions, a formal system can't be equipped with a truth predicate $\text{True}$ such that $\text{True}(G)$ if and only if $G$ is true. The reason is that under suitable assumptions, we can write down a sentence $G$ which is equivalent to $\text{True}(\neg G)$ (the liar paradox), and then we obtain a contradiction.

Christiano, Yudkowsky, Herreshoff, and Barasz recently showed, however, that a formal system can be equipped with a probability predicate $\mathbb{P}(G)$ satisfying a weaker reflection principle, namely that

$$\mathbb{P}(G) \in (a, b) \Leftrightarrow \mathbb{P}(\mathbb{P}(G) \in (a, b)) = 1.$$

The corresponding probability assignments to sentences may be thought of as probability distributions over models of some theory. See the draft for more details. (Disclaimer: I was involved in a small way with a workshop one of whose goals was to see how far this result could be pushed.)

What are your favorite instructional counterexamples?

2010-03-02T05:57:45Z

Related: question #879, Most interesting mathematics mistake. But the intent of this question is more pedagogical.

In many branches of mathematics, it seems to me that a good counterexample can be worth just as much as a good theorem or lemma. The only branch where I think this is explicitly recognized in the literature is topology, where for example Munkres is careful to point out and discuss his favorite counterexamples in his book, and Counterexamples in Topology is quite famous. The art of coming up with counterexamples, especially minimal counterexamples, is in my mind an important one to cultivate, and perhaps it is not emphasized enough these days.

So: what are your favorite examples of counterexamples that really illuminate something about some aspect of a subject?

Bonus points if the counterexample is minimal in some sense, bonus points if you can make this sense rigorous, and extra bonus points if the counterexample was important enough to impact yours or someone else's research, especially if it was simple enough to present in an undergraduate textbook.

As usual, please limit yourself to one counterexample per answer.

Answer by Qiaochu Yuan for Fixed point theorems

2013-04-11T01:44:16Z

Here is a teeny tiny toy version of the Lefschetz fixed point theorem: let $f : S \to S$ be an endomorphism of a finite set and let $K[f] : K[S] \to K[S]$ be the induced linear map on free vector spaces. Then $\text{tr}(K[f])$ is the number of fixed points of $f$. This is one way to prove Burnside's lemma.

Answer by Qiaochu Yuan for Is there an analog of determinant for linear operators in infinite dimensions as that of finite dimensions?

2013-04-04T04:57:19Z

I am trying to find out the essence of what a determinant is.

The abstract way to define the determinant of a linear operator $T : V \to V$ of a finite-dimensional vector space is that it is the induced action of $T$ on the top exterior power $\Lambda^n(T) : \Lambda^n(V) \to \Lambda^n(V)$, where $n = \dim V$. The top exterior power is $1$-dimensional, so $\Lambda^n(T)$ is canonically a scalar. By functoriality of the exterior power, $T \mapsto \Lambda^n(T)$ is a monoid homomorphism, which is why it detects invertibility.

So you can see what the problem is in infinite dimensions: if $V$ is infinite-dimensional, there is no top exterior power! All the exterior powers are also infinite-dimensional.

Extremely messy proofs

2010-10-27T16:01:38Z

Currently in my undergraduate courses I am being taught how to set up various machinery using slick, short proofs and then how to apply that machinery. What I am not being taught, largely, is what came before these slick, short proofs. What did mathematicians do before so-and-so proved such-and-such lemma? Where, in other words, are the tedious, long proofs that we can look to as examples of the horrible mess we are escaping? What insights helped mathematicians escape those messes?

Right now I am particularly interested in examples from measure theory. What did people do before, for example, Dynkin's lemma or Caratheodory's extension theorem? Or were these tools available from near the start?

An answer should include both some indication of how tedious and long the old approach was and how much slicker and shorter the modern approach is. Ideally, it should also discuss how the transition between the two happened.

(If you prefer the old approach to the modern approach, for example for pedagogical reasons, that would also be interesting to hear about.)

Answer by Qiaochu Yuan for A strange equality of the operator E ($Eu_n=u_{n+1}$)

2013-03-23T19:07:14Z

$E$ acts on the finite-dimensional vector space consisting of sequences satisfying that recurrence relation, and those are its eigenvalues on that space. More generally, $E$ acts on the nullspace of $p(E)$ for any polynomial $p$ with eigenvalues the roots of $p$, and you can use this together with the theory of Jordan normal form to write down general solutions to linear recurrence relations.

Where does a math person go to learn quantum mechanics?

2009-10-27T22:29:58Z

My undergraduate advisor said something very interesting to me the other day; it was something like "not knowing quantum mechanics is like never having heard a symphony." I've been meaning to learn quantum for some time now, and after seeing it come up repeatedly in mathematical contexts like Scott Aaronson's blog or John Baez's TWF, I figure I might as well do it now.

Unfortunately, my physics background is a little lacking. I know some mechanics and some E&M, but I can't say I've mastered either (for example, I don't know either the Hamiltonian or the Lagrangian formulations of mechanics). I also have a relatively poor background in differential equations and multivariate calculus. However, I do know a little representation theory and a little functional analysis, and I like q-analogues! (This last comment is somewhat tongue-in-cheek.)

Given this state of affairs, what's my best option for learning quantum? Can you recommend me a good reference that downplays the historical progression and emphasizes the mathematics? Is it necessary that I understand what a Hamiltonian is first?

(I hope this is "of interest to mathematicians." Certainly the word "quantum" gets thrown around enough in mathematics papers that I would think it is.)

What do heat kernels have to do with the Riemann-Roch theorem and the Gauss-Bonnet theorem?

2010-02-08T23:54:01Z

I know the following facts. (Don't assume I know much more than the following facts.)

The Atiyah-Singer index theorem generalizes both the Riemann-Roch theorem and the Gauss-Bonnet theorem.
The Atiyah-Singer index theorem can be proven using heat kernels.

This implies that both Riemann-Roch and Gauss-Bonnet can be proven using heat kernels. Now, I don't think I have the background necessary to understand the details of the proofs, but I would really appreciate it if someone briefly outlined for me an extremely high-level summary of how the above two proofs might go. Mostly what I'm looking for is physical intuition: when does one know that heat kernel methods are relevant to a mathematical problem? Is the mathematical problem recast as a physical problem to do so, and how?

(Also, does one get Riemann-Roch for Riemann surfaces only or can we also prove the version for more general algebraic curves?)

Edit: Sorry, the original question was a little unclear. While I appreciate the answers so far concerning how one gets from heat kernels to the index theorem to the two theorems I mentioned, I'm wondering what one can say about going from heat kernels directly to the two theorems I mentioned. As Deane mentions in this comments, my hope is that this reduces the amount of formalism necessary to the point where the physical ideas are clear to someone without a lot of background.

How do I make the conceptual transition from multivariable calculus to differential forms?

2010-01-03T10:11:45Z

One way to define the algebra of differential forms $\Omega(M)$ on a smooth manifold $M$ (as explained by John Baez's week287) is as the exterior algebra of the dual of the module of derivations on the algebra $C^{\infty}(M)$ of smooth functions $M \to \mathbb{R}$. Given that derivations are vector fields, 1-forms send vector fields to smooth functions, and some handwaving about area elements suggests that k-forms should be built from 1-forms in an anticommutative fashion, I am almost willing to accept this definition as properly motivated.

One can now define the exterior derivative $d : \Omega(M) \to \Omega(M)$ by defining $d(f dg_1 ... dg_k) = df dg_1 ... dg_k$ and extending by linearity. I am almost willing to accept this definition as properly motivated as well.

Now, the exterior derivative (together with the Hodge star and some fiddling) generalizes the three main operators of multivariable calculus: the divergence, the gradient, and the curl. My intuition about the definitions and properties of these operators comes mostly from basic E&M, and when I think about the special cases of Stokes' theorem for div, grad, and curl, I think about the "physicist's proofs." What I'm not sure how to do, though, is to relate this down-to-earth context with the high-concept algebraic context described above.

Question: How do I see conceptually that differential forms and the exterior derivative, as defined above, naturally have physical interpretations generalizing the "naive" physical interpretations of the divergence, the gradient, and the curl? (By "conceptually" I mean that it is very unsatisfying just to write down the definitions and compute.) And how do I gain physical intuition for the generalized Stokes' theorem?

(An answer in the form of a textbook that pays special attention to the relationship between the abstract stuff and the physical intuition would be fantastic.)

Answer by Qiaochu Yuan for Multivariate functions whose value is independent of the order of the arguments

2013-03-13T05:19:26Z

I don't understand why you say that $f$ is continuous if its inputs are positive integers. Anyway, you can take any symmetric polynomial in the $g(r_i)$, e.g. $\sum_{i < j} g(r_i) g(r_j)$.

Answer by Qiaochu Yuan for Rigid monoidal abelian category without an exact tensor functor to Vect

2013-02-22T04:48:48Z

Let $C$ be a fusion category with simple objects $X_i$. If $X$ is an object, then $X \otimes X_i = \bigoplus N_{ij} X_j$ for some matrix $N_{ij}$ of non-negative integers. The largest non-negative real eigenvalue of this matrix is called the Frobenius-Perron dimension $\dim X$ of $X$. It is preserved by exact tensor functors (Corollary 4.6 in the linked paper) and coincides with the ordinary dimension for finite-dimensional vector spaces. It follows that a fusion category with an object whose Frobenius-Perron dimension is not an integer does not admit an exact tensor functor to $\text{FinVect}$. If I'm not mistaken, tensor functors preserve dualizable objects, so any tensor functor to $\text{Vect}$ must land in $\text{FinVect}$ anyway, and the conclusion follows.

In particular there is a fusion category with an object $X$ satisfying $X^{\otimes 2} \cong 1 \oplus X$ whose Frobenius-Perron dimension is $\frac{1 + \sqrt{5}}{2}$.

Edit: Here is maybe a simpler way of putting it. Associated to any fusion category $C$ is its Grothendieck ring, and an exact tensor functor between fusion categories gives a homomorphism of Grothendieck rings. So it suffices to find a fusion category whose Grothendieck ring does not admit a homomorphism to $\mathbb{Z}$, and clearly a fusion category with an object $X$ satisfying $X^{\otimes 2} \cong 1 \oplus X$ has this property.

Edit #2: It seems that in the literature a Tannakian category is required to be symmetric monoidal. In this case, ignore everything I said above.

Deligne (see e.g. this exposition by Ostrik) showed that over an algebraically closed field of characteristic $0$ together with some other mild hypotheses, which hold in particular for symmetric fusion categories, any such category admits a super fiber functor to $\text{sVect}$. From here one can classify symmetric fusion categories in terms of finite groups; see section 2.12 of On braided fusion categories I by Drinfeld, Gelaki, Nikshych, and Ostrik. $\text{sVect}$ itself does not admit an ordinary fiber functor, as Angelo pointed out; the obvious functor doesn't preserve symmetries.

Does any method of summing divergent series work on the harmonic series?

2009-10-29T03:35:18Z

It's sort of folklore (as exemplified by this old post at The Everything Seminar) that none of the common techniques for summing divergent series work to give a meaningful value to the harmonic series, and it's also sort of folklore (although I can't remember where I heard this) that the harmonic series is more or less the only important series with this property.

What other methods besides analytic continuation and zeta regularization exist for summing divergent series? Do they work on the harmonic series? And are there other well-known series which also don't have obvious regularizations?

Combinatorial results without known combinatorial proofs

2009-11-13T22:42:44Z

Stanley likes to keep a list of combinatorial results for which there is no known combinatorial proof. For example, until recently I believe the explicit enumeration of the de Brujin sequences fell into this category (but now see arXiv:0910.3442v1). Many unimodality results also fall into this category. Do you know of any other results of this kind, especially results that look frustratingly like they ought to have simple combinatorial proofs?

For the purposes of this question, "combinatorial result" should be interpreted as meaning some kind of exact enumeration, and "combinatorial proof" should be interpreted as meaning, more or less, "bijective proof." (So for example I am not interested in bounds on Ramsey numbers.)

Answer by Qiaochu Yuan for Ring with three binary operations

2013-02-05T19:25:59Z

The claim that there are two binary operations on rings is misleading. Rings are actually equipped with countably many $n$-ary operations, one for each noncommutative polynomial in $n$ variables over $\mathbb{Z}$. These generate the morphisms in a category with finite products, the Lawvere theory of rings $T$, which is a category with the property that finite product-preserving functors $T \to \text{Set}$ are the same thing as rings. It just happens to be the case that as a category with finite products, $T$ is generated by addition and multiplication. The Lawvere theory of commutative rings is similar except that the polynomials are commutative; incidentally, it may also be regarded as the category of affine spaces over $\mathbb{Z}$.

This gives a useful perspective from which to understand other ring-like structures. For example:

commutative Banach algebras are equipped with an $n$-ary operation for each holomorphic function $\mathbb{C}^n \to \mathbb{C}$.
smooth algebras like the algebras $C^{\infty}(M)$ of smooth functions on a smooth manifold are equipped with an $n$-ary operation for each smooth function $\mathbb{R}^n \to \mathbb{R}$.

Here is a general procedure for determining what operations are actually available to you when working with some mathematical objects. If $C$ is a concrete category and $F : C \to \text{Set}$ the forgetful functor, then one interpretation of "$n$-ary operation" is "natural transformation $F^n \to F$." If $C$ has finite coproducts and $F$ is representable by an object $a$, then by the Yoneda lemma these are the same thing as elements of $F(a \sqcup ... \sqcup a)$. This reproduces the obvious answers for groups, rings, etc., and when $C$ is the opposite of the category of smooth manifolds and $F : M \mapsto C^{\infty}(M)$ then we get that "$n$-ary operation" means element of $C^{\infty}(\mathbb{R}^n)$ as above.

Answer by Qiaochu Yuan for Elementary applications of linear algebra over finite fields

2013-01-14T22:11:45Z

Suppose you want to compute the period of the Fibonacci sequence $\bmod p$. This reduces to examining the powers of the matrix $\left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right]$ over $\mathbb{F}_p$, which requires either diagonalizing it over $\mathbb{F}_p$ or over $\mathbb{F}_{p^2}$ (or, when $p = 5$, using a nontrivial Jordan block). From here you can write down a nice number that is divisible by the period, depending on the value of $p \bmod 5$ (this uses a little quadratic reciprocity).

Edit: I suppose this requires some number-theoretic background to do properly. Never mind.

Different definitions of the dimension of an algebra

2009-10-25T22:02:19Z

I know of three ways to define the dimension of a finitely-generated commutative algebra A over a field F:

The Gelfand-Kirillov (GK) dimension, based on the growth of the Hilbert function.
The Krull dimension, based on chains of prime ideals.
The transcendence degree of the fraction field of A over F.

According to Artin, GK dimension is the most robust notion because it applies to certain noncommutative algebras. And in the noncommutative setting one can't form fraction fields, so the transcendence degree is out of the question (right?).

But Krull dimension has the advantage that it applies to arbitrary rings. As far as I can tell, the definition of GK dimension only applies to algebras. So: as a matter of pedagogy, which notion of dimension is most appropriate for what applications? Which is easiest to prove things about when?

Answer by Qiaochu Yuan for Why the preimage rather than image in Stone-type dualities.

2013-01-09T23:47:14Z

You should think of the preimage as taking the pullback of $\mathbb{F}_2$-valued functions. For any topological space $X$, the space of continuous functions $X \to \mathbb{F}_2$ may be identified with the Boolean algebra / ring of clopen subsets of $X$, the pullback of such a function is another such function, and taking pullbacks corresponds to taking preimages (thinking of subsets via their indicator functions). The natural thing to do with functions is pull them back, both in logic and in geometry. Moreover, pulling back functions is a ring homomorphism, and even in contexts where pushing forward functions can also be done it usually does not preserve multiplication.

Edit: As for relations instead of sets, taking the transpose of a relation gives an equivalence of categories $\text{Rel} \cong \text{Rel}^{op}$ ($\text{Rel}$ is a dagger category) which exchanges inverse image and image, so in that sense there isn't a strong reason to prefer one over the other for relations.

Answer by Qiaochu Yuan for Why is the Leibniz rule a definition for derivations?

2012-12-28T01:31:58Z

Let $A$ be an algebra over a field $k$, such as $C^{\infty}(M)$ for $k = \mathbb{R}$. You should think of "points" as meaning $k$-algebra homomorphisms $A \to k$ and "one-parameter families of points" as meaning $k$-algebra homomorphisms $A \to k[t]$ (at least in a more algebraic setting). The intuitive meaning of "tangent vector" is "infinitesimal one-parameter family of points," and algebraically this means a morphism $A \to k[t]/t^2$. The Leibniz rule is equivalent to the statement that this homomorphism preserves products.

The more fundamental property is really the chain rule, but note that linearity and the Leibniz rule are equivalent to the chain rule for polynomials, and in an algebraic setting polynomials are the only things available. In a less algebraic setting, e.g. smooth manifolds, it's actually more natural to require the chain rule for all smooth functions; this is closely related to the idea that $C^{\infty}(M)$ is not really an algebra but a smooth algebra.

Identifying poisoned wines

2011-03-29T04:18:43Z

The standard version of this puzzle is as follows: you have $1000$ bottles of wine, one of which is poisoned. You also have a supply of rats (say). You want to determine which bottle is the poisoned one by feeding the wines to the rats. The poisoned wine takes exactly one hour to work and is undetectable before then. How many rats are necessary to find the poisoned bottle in one hour?

It is not hard to see that the answer is $10$. Way back when math.SE first started, a generalization was considered where more than one bottle of wine is poisoned. The strategy that works for the standard version fails for this version, and I could only find a solution for the case of $2$ poisoned bottles that requires $65$ rats. Asymptotically my solution requires $O(\log^2 N)$ rats to detect $2$ poisoned bottles out of $N$ bottles.

Can anyone do better asymptotically and/or prove that their answer is optimal and/or find a solution that works for more poisoned bottles? The number of poisoned bottles, I guess, should be kept constant while the total number of bottles is allowed to become large for asymptotic estimates.

Answer by Qiaochu Yuan for Spectra of elements of a Banach algebra and the role played by the Hahn-Banach Theorem.

2012-12-19T03:15:20Z

I do not believe that the Hahn-Banach theorem is necessary. At some point I had planned on writing up a blog post verifying this but I lost the motivation...

The idea is that you can prove Liouville's theorem in the Banach space setting directly without using Hahn-Banach to reduce to the case of $\mathbb{C}$ (I asked whether this was possible in this math.SE question). Most of the steps in the proof are exactly the same; the only one that isn't, as far as I can tell, is the fundamental theorem of calculus, which is usually proven using the mean value theorem but which can instead be proven following the answers to this math.SE question.

Answer by Qiaochu Yuan for Can FLT fail with a parametrization over some extension of Z?

2012-12-17T11:19:01Z

No; in fact, you can take $K = \mathbb{C}$. This follows from the Mason-Stothers theorem in the same way that FLT for sufficiently large $n$ follows from the abc conjecture.

As Chandan indicates in the comments, a more geometric reason this is false is that the Fermat curves $x^n + y^n = z^n$ have positive genus for $n \ge 3$ and hence do not admit rational parameterizations (over fields of characteristic zero or something like that).

Is there a high-concept explanation for why characteristic 2 is special?

2009-10-17T18:55:01Z

The structure of the multiplicative groups of Z/pZ or of Z_p is the same for odd primes, but not for 2. Quadratic reciprocity has a uniform statement for odd primes, but an extra statement for 2. So in these examples characteristic 2 is a messy special case.

On the other hand, certain types of combinatorial questions can be reduced to linear algebra over F₂, and this relationship doesn't seem to generalize to other finite fields. So in this example characteristic 2 is a nice special case.

Is anything deep going on here? (I have a vague idea here about additive inverses and Fourier analysis over Z/2Z, but I'll wait to see what other people say.)

Answer by Qiaochu Yuan for Integrating Powers without much Calculus

2012-11-28T07:47:45Z

This may not be in the spirit of what you want, but... by scaling arguments it suffices to establish that $\int_0^1 x^p dx = \frac{1}{p + 1}$. Consider the following probabilistic argument (not entirely rigorous but very suggestive): the integral describes the probability that if you choose $p + 1$ points uniformly at random in the interval $[0, 1]$, then the first point you chose is the rightmost. (If the first point you chose is $x$, then the probability that each of the remaining $p$ points is to the left of $x$ is $x^p$.)

On the other hand, you can choose the points simultaneously and then decide which one was the first point you chose. You'll end up choosing the rightmost point with probability $\frac{1}{p + 1}$.

A rigorous version of this argument proceeds by partitioning $[0, 1]^{p+1}$ into $p + 1$ parts of the same measure depending on which of the coordinates is the largest and then observing that the measure of one of these parts can be expressed using the above integral. I admit I cannot readily visualize these parts even for $p = 2$...

Answer by Qiaochu Yuan for Free Objects in Functor Categories

2012-11-21T09:43:43Z

$[C, \text{Ab}]$ admits a forgetful functor to $[\text{Ob}(C), \text{Set}]$ (where $\text{Ob}(C)$ denotes the category with the same objects as $C$ but no non-identity morphisms). This is a direct generalization of the module case, which corresponds to taking $C$ to have one object. The corresponding free objects are coproducts of representables.

Comment by Qiaochu Yuan

2013-05-24T20:43:11Z

The question seems vague. Can you be more specific?

Comment by Qiaochu Yuan

2013-05-21T20:40:21Z

Here's one possibility: consider the Grothendieck group of the category of finite groups, where $[A] = [B] + [C]$ whenever there is a short exact sequence $0 \to B \to A \to C \to 0$. Then the Grothendieck group should be free abelian on the finite simple groups, and the image of a finite group in the Grothendieck group should be precisely the simple groups in a composition series, with appropriate multiplicities.

Comment by Qiaochu Yuan

2013-05-21T18:36:05Z

I think these "ghost representations" do exist; the literature on fusion categories might be a place to find them?

Comment by Qiaochu Yuan

2013-05-21T04:05:02Z

The fundamental group can be recovered from the category of covering spaces; it's the unique group $G$ such that the category of covering spaces is equivalent to $G\text{-Set}$. In that sense it doesn't depend on a choice of basepoint.

Comment by Qiaochu Yuan

2013-05-19T05:53:57Z

This sounds quite hard. Isn't the category of finitely generated commutative idempotent monoids equivalent to the category of finite lattices?

Comment by Qiaochu Yuan

2013-05-17T18:28:46Z

I'm not sure (I meant to work this out sometime but haven't gotten around to it). Some Cartesian closed category where the morphisms are computable functions. The point would be that Godel numbering provides something like a surjection $\mathbb{N} \to \mathbb{N}^{\mathbb{N}}$ in such a category, so $\mathbb{N}$ must have the fixed point property.

Comment by Qiaochu Yuan

2013-05-17T04:30:31Z

Does this count as a proof at the undergraduate level?

Comment by Qiaochu Yuan

2013-05-17T04:26:20Z

The recursion theorem ought to be a corollary of Lawvere's fixed point theorem, right?

Comment by Qiaochu Yuan

2013-05-15T20:31:00Z

I think Igor Pak (?) once said something like "gambling is the applied representation theory of the symmetric group," but I don't have a citation so I may have just imagined this.

Comment by Qiaochu Yuan

2013-05-13T03:34:24Z

The options are not NP-complete and P. There are plausible candidates for problems of intermediate difficulty, e.g. factoring.

Comment by Qiaochu Yuan

2013-05-11T07:01:50Z

@Tony: is it? That isn't clear to me. What embedding do you have in mind?

Comment by Qiaochu Yuan

2013-05-07T02:43:10Z

@Yemon: yes, and I don't remember. I think parts of the argument come up in the McKay correspondence.

Comment by Qiaochu Yuan

2013-05-05T05:15:40Z

Perhaps en.wikipedia.org/wiki/Hausdorff_moment_problem is relevant?

Comment by Qiaochu Yuan

2013-05-01T23:34:01Z

This question belongs on stats.stackexchange.com .

Comment by Qiaochu Yuan

2013-04-24T02:09:09Z

Oog, that's hard to read. Try $DAD$ instead?