User qiaochu yuan - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T17:42:04Z http://mathoverflow.net/feeds/user/290 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/131255/objects-which-cant-be-defined-without-making-choices-but-which-end-up-independen/131278#131278 Answer by Qiaochu Yuan for objects which can't be defined without making choices but which end up independent of the choice Qiaochu Yuan 2013-05-20T22:04:39Z 2013-05-20T22:04:39Z <p>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. </p> http://mathoverflow.net/questions/130883/is-there-any-proof-that-you-feel-you-do-not-understand/130907#130907 Answer by Qiaochu Yuan for Is there any proof that you feel you do not "understand"? Qiaochu Yuan 2013-05-17T04:38:23Z 2013-05-17T04:38:23Z <p>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.</p> <p>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." </p> <p>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$. </p> <p>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.) </p> http://mathoverflow.net/questions/130643/is-it-true-that-nature-promotes-products/130645#130645 Answer by Qiaochu Yuan for Is it true that Nature promotes products? Qiaochu Yuan 2013-05-14T23:06:18Z 2013-05-14T23:21:44Z <p>You need to distinguish between "coproduct" and "comultiplication." The categorical coproduct is just a generalization of addition and is intuitive in many contexts. </p> <p>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...</p> <p>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 <em>contravariant</em> monoidal functor, so... </p> <hr> <p>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</p> <p>$$x^n \mapsto \sum_k x^k \otimes x^{n-k}$$</p> <p>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</p> <p>$$x^n \mapsto \sum_k {n \choose k} x^k \otimes x^{n-k}$$</p> <p>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$. </p> <p>In the same spirit, Rota noticed that the <a href="http://en.wikipedia.org/wiki/Incidence_algebra" rel="nofollow">incidence algebra</a> 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</p> <p>$$[a, b] \mapsto \sum_{a \le c \le b} [a, c] \otimes [c, b]$$</p> <p>and this reflects the process of breaking apart an interval into two subintervals. </p> <hr> <p>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). </p> <p>Comultiplications only seem unfamiliar because they were historically not pointed out, but actually they are all over the place. See also <a href="http://mathoverflow.net/questions/76509/what-is-a-coalgebra-intuitively" rel="nofollow">What is a coalgebra intuitively?</a></p> http://mathoverflow.net/questions/16735/is-a-non-analytic-proof-of-dirichlets-theorem-on-primes-known-or-possible Is a "non-analytic" proof of Dirichlet's theorem on primes known or possible? Qiaochu Yuan 2010-03-01T02:02:18Z 2013-05-08T15:34:47Z <p>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, <a href="http://www.math.uconn.edu/~kconrad/blurbs/gradnumthy/dirichleteuclid.pdf" rel="nofollow">this paper</a> of K. Conrad) that this is possible precisely for the primes congruent to $a \bmod n$ where $a^2 \equiv 1 \bmod n$. </p> <p>However, the result about polynomials having infinitely many prime divisors has the following generalization: <strong>any</strong> 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. </p> <p><strong>Question 1:</strong> 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 <em>efficiently</em> 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. </p> <p><strong>Question 2:</strong> 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.)</p> <p>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 <strong>at least one</strong> 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. </p> http://mathoverflow.net/questions/128439/does-this-kind-of-endofunctor-ever-have-an-initial-algebra Does this kind of endofunctor ever have an initial algebra? Qiaochu Yuan 2013-04-23T06:04:30Z 2013-04-26T13:14:56Z <p>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?) </p> <p>The motivation for this question is a somewhat long story, but if someone wants I can edit it in.</p> <p>Note that if $C = \text{Set}$ then this is impossible by Cantor's theorem (and Lambek's theorem). I'm worried that the <a href="http://mathoverflow.net/questions/127045/fixed-point-theorems/127103#127103" rel="nofollow">Lawvere fixed point theorem</a> can shoot down this question as well. </p> http://mathoverflow.net/questions/128260/tannaka-duality-for-c-algebras/128280#128280 Answer by Qiaochu Yuan for Tannaka duality for C*-algebras? Qiaochu Yuan 2013-04-21T20:06:54Z 2013-04-21T20:06:54Z <p>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. </p> <p><strong>Theorem:</strong> 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.)</p> <p><em>Proof.</em> 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$</p> <p>(And of course if you forget the forgetful functor then you cannot recover $R$ at all, only its Morita equivalence class.) </p> <p>"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 <em>a priori</em> should only let us at best recover the group algebra; we need more structure (e.g. the tensor product) to recover the group itself.</p> http://mathoverflow.net/questions/127931/age-of-stochasticity/127936#127936 Answer by Qiaochu Yuan for Age of Stochasticity? Qiaochu Yuan 2013-04-18T08:12:56Z 2013-04-18T08:12:56Z <p>Here is a result that gives the flavor of the kind of thing along these lines I hope to see in the future. Recall <a href="http://en.wikipedia.org/wiki/Tarski%27s_undefinability_theorem" rel="nofollow">Tarski's undefinability of truth</a>: 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. </p> <p>Christiano, Yudkowsky, Herreshoff, and Barasz recently showed, however, that a formal system <em>can</em> be equipped with a probability predicate $\mathbb{P}(G)$ satisfying a weaker reflection principle, namely that</p> <p>$$\mathbb{P}(G) \in (a, b) \Leftrightarrow \mathbb{P}(\mathbb{P}(G) \in (a, b)) = 1.$$</p> <p>The corresponding probability assignments to sentences may be thought of as probability distributions over models of some theory. See <a href="http://intelligence.org/wp-content/uploads/2013/03/Christiano-et-al-Naturalistic-reflection-early-draft.pdf" rel="nofollow">the draft</a> 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.) </p> http://mathoverflow.net/questions/16829/what-are-your-favorite-instructional-counterexamples What are your favorite instructional counterexamples? Qiaochu Yuan 2010-03-02T05:57:45Z 2013-04-12T13:54:59Z <p>Related: question #879, <a href="http://mathoverflow.net/questions/879/most-interesting-mathematics-mistake" rel="nofollow">Most interesting mathematics mistake</a>. But the intent of this question is more pedagogical.</p> <p>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 <em>Counterexamples in Topology</em> 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.</p> <p>So: what are your favorite examples of counterexamples that really illuminate something about some aspect of a subject? </p> <p>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. </p> <p>As usual, please limit yourself to <strong>one counterexample per answer.</strong> </p> http://mathoverflow.net/questions/127045/fixed-point-theorems/127172#127172 Answer by Qiaochu Yuan for Fixed point theorems Qiaochu Yuan 2013-04-11T01:44:16Z 2013-04-11T01:44:16Z <p>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.</p> http://mathoverflow.net/questions/126464/is-there-an-analog-of-determinant-for-linear-operators-in-infinite-dimensions-as/126473#126473 Answer by Qiaochu Yuan for Is there an analog of determinant for linear operators in infinite dimensions as that of finite dimensions? Qiaochu Yuan 2013-04-04T04:57:19Z 2013-04-04T04:57:19Z <blockquote> <p>I am trying to find out the essence of what a determinant is. </p> </blockquote> <p>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 <a href="http://en.wikipedia.org/wiki/Exterior_algebra#The_exterior_power" rel="nofollow">exterior power</a> $\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.</p> <p>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. </p> http://mathoverflow.net/questions/43820/extremely-messy-proofs Extremely messy proofs Qiaochu Yuan 2010-10-27T16:01:38Z 2013-03-23T22:16:26Z <p>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? </p> <p>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?</p> <p>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.</p> <p>(If you <em>prefer</em> the old approach to the modern approach, for example for pedagogical reasons, that would also be interesting to hear about.)</p> http://mathoverflow.net/questions/125390/a-strange-equality-of-the-operator-e-eu-nu-n1/125395#125395 Answer by Qiaochu Yuan for A strange equality of the operator E ($Eu_n=u_{n+1}$) Qiaochu Yuan 2013-03-23T19:07:14Z 2013-03-23T19:07:14Z <p>$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. </p> http://mathoverflow.net/questions/2917/where-does-a-math-person-go-to-learn-quantum-mechanics Where does a math person go to learn quantum mechanics? Qiaochu Yuan 2009-10-27T22:29:58Z 2013-03-23T15:20:14Z <p>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.</p> <p>Unfortunately, my physics background is a little lacking. I know some mechanics and some E&amp;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.)</p> <p>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?</p> <p>(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.)</p> http://mathoverflow.net/questions/14714/what-do-heat-kernels-have-to-do-with-the-riemann-roch-theorem-and-the-gauss-bonne What do heat kernels have to do with the Riemann-Roch theorem and the Gauss-Bonnet theorem? Qiaochu Yuan 2010-02-08T23:54:01Z 2013-03-23T07:02:04Z <p>I know the following facts. (Don't assume I know much more than the following facts.)</p> <ul> <li>The Atiyah-Singer index theorem generalizes both the Riemann-Roch theorem and the Gauss-Bonnet theorem.</li> <li>The Atiyah-Singer index theorem can be proven using heat kernels.</li> </ul> <p>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? </p> <p>(Also, does one get Riemann-Roch for Riemann surfaces only or can we also prove the version for more general algebraic curves?)</p> <p><strong>Edit:</strong> 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 <strong>directly</strong> 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.</p> http://mathoverflow.net/questions/10574/how-do-i-make-the-conceptual-transition-from-multivariable-calculus-to-differenti How do I make the conceptual transition from multivariable calculus to differential forms? Qiaochu Yuan 2010-01-03T10:11:45Z 2013-03-23T06:56:44Z <p>One way to define the algebra of differential forms $\Omega(M)$ on a smooth manifold $M$ (as explained by John Baez's <a href="http://math.ucr.edu/home/baez/week287.html" rel="nofollow">week287</a>) 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 <strong>almost</strong> willing to accept this definition as properly motivated. </p> <p>One can now define the exterior derivative $d : \Omega(M) \to \Omega(M)$ by defining $d(f &nbsp; dg_1 &nbsp; ... &nbsp; dg_k) = df &nbsp; dg_1 &nbsp; ... &nbsp; dg_k$ and extending by linearity. I am <strong>almost</strong> willing to accept this definition as properly motivated as well. </p> <p>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&amp;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.</p> <p><strong>Question:</strong> 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?</p> <p>(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.)</p> http://mathoverflow.net/questions/124384/multivariate-functions-whose-value-is-independent-of-the-order-of-the-arguments/124385#124385 Answer by Qiaochu Yuan for Multivariate functions whose value is independent of the order of the arguments Qiaochu Yuan 2013-03-13T05:19:26Z 2013-03-13T05:19:26Z <p>I don't understand why you say that $f$ is continuous if its inputs are positive integers. Anyway, you can take any <a href="http://en.wikipedia.org/wiki/Symmetric_polynomial" rel="nofollow">symmetric polynomial</a> in the $g(r_i)$, e.g. $\sum_{i &lt; j} g(r_i) g(r_j)$. </p> http://mathoverflow.net/questions/122596/rigid-monoidal-abelian-category-without-an-exact-tensor-functor-to-vect/122598#122598 Answer by Qiaochu Yuan for Rigid monoidal abelian category without an exact tensor functor to Vect Qiaochu Yuan 2013-02-22T04:48:48Z 2013-02-22T06:24:41Z <p>Let $C$ be a <a href="http://ncatlab.org/nlab/show/fusion+category" rel="nofollow">fusion category</a> 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 <a href="http://arxiv.org/abs/math/0401246" rel="nofollow">Frobenius-Perron dimension</a> $\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. </p> <p>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}$. </p> <p><strong>Edit:</strong> 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.</p> <p><strong>Edit #2:</strong> It seems that in the literature a Tannakian category is required to be <em>symmetric</em> monoidal. In this case, ignore everything I said above. </p> <p>Deligne (see e.g. <a href="http://arxiv.org/abs/math/0401347" rel="nofollow">this exposition by Ostrik</a>) 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 <em>super</em> fiber functor to $\text{sVect}$. From here one can classify symmetric fusion categories in terms of finite groups; see section 2.12 of <a href="http://arxiv.org/abs/0906.0620" rel="nofollow">On braided fusion categories I</a> 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. </p> http://mathoverflow.net/questions/3204/does-any-method-of-summing-divergent-series-work-on-the-harmonic-series Does any method of summing divergent series work on the harmonic series? Qiaochu Yuan 2009-10-29T03:35:18Z 2013-02-21T01:03:12Z <p>It's sort of folklore (as exemplified by <a href="http://cornellmath.wordpress.com/2007/08/02/sum-divergent-series-iii/" rel="nofollow">this old post</a> 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.</p> <p>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?</p> http://mathoverflow.net/questions/5449/combinatorial-results-without-known-combinatorial-proofs Combinatorial results without known combinatorial proofs Qiaochu Yuan 2009-11-13T22:42:44Z 2013-02-10T22:17:01Z <p>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 <a href="http://en.wikipedia.org/wiki/De_Bruijn_sequence" rel="nofollow">de Brujin sequences</a> fell into this category (but now see <a href="http://arxiv.org/pdf/0910.3442" rel="nofollow">arXiv:0910.3442v1</a>). 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?</p> <p>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.)</p> http://mathoverflow.net/questions/120875/ring-with-three-binary-operations/120903#120903 Answer by Qiaochu Yuan for Ring with three binary operations Qiaochu Yuan 2013-02-05T19:25:59Z 2013-02-06T04:19:29Z <p>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 <a href="http://ncatlab.org/nlab/show/Lawvere+theory" rel="nofollow">Lawvere theory</a> 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}$. </p> <p>This gives a useful perspective from which to understand other ring-like structures. For example:</p> <ul> <li>commutative Banach algebras are equipped with an $n$-ary operation for each holomorphic function $\mathbb{C}^n \to \mathbb{C}$.</li> <li><a href="http://ncatlab.org/nlab/show/smooth+algebra" rel="nofollow">smooth algebras</a> 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}$. </li> </ul> <p>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. </p> http://mathoverflow.net/questions/118903/elementary-applications-of-linear-algebra-over-finite-fields/118927#118927 Answer by Qiaochu Yuan for Elementary applications of linear algebra over finite fields Qiaochu Yuan 2013-01-14T22:11:45Z 2013-01-15T00:31:44Z <p>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 &amp; 1 \\ 1 &amp; 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). </p> <p><strong>Edit:</strong> I suppose this requires some number-theoretic background to do properly. Never mind. </p> http://mathoverflow.net/questions/2525/different-definitions-of-the-dimension-of-an-algebra Different definitions of the dimension of an algebra Qiaochu Yuan 2009-10-25T22:02:19Z 2013-01-12T22:21:44Z <p>I know of three ways to define the dimension of a finitely-generated commutative algebra A over a field F:</p> <ul> <li>The Gelfand-Kirillov (GK) dimension, based on the growth of the Hilbert function.</li> <li>The Krull dimension, based on chains of prime ideals.</li> <li>The transcendence degree of the fraction field of A over F.</li> </ul> <p>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?).</p> <p>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?</p> http://mathoverflow.net/questions/118486/why-the-preimage-rather-than-image-in-stone-type-dualities/118487#118487 Answer by Qiaochu Yuan for Why the preimage rather than image in Stone-type dualities. Qiaochu Yuan 2013-01-09T23:47:14Z 2013-01-10T04:25:39Z <p>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. </p> <p><strong>Edit:</strong> As for relations instead of sets, taking the <a href="http://en.wikipedia.org/wiki/Inverse_relation" rel="nofollow">transpose</a> of a relation gives an equivalence of categories $\text{Rel} \cong \text{Rel}^{op}$ ($\text{Rel}$ is a <a href="http://en.wikipedia.org/wiki/Dagger_category" rel="nofollow">dagger category</a>) which exchanges inverse image and image, so in that sense there isn't a strong reason to prefer one over the other for relations. </p> http://mathoverflow.net/questions/117374/why-is-the-leibniz-rule-a-definition-for-derivations/117375#117375 Answer by Qiaochu Yuan for Why is the Leibniz rule a definition for derivations? Qiaochu Yuan 2012-12-28T01:31:58Z 2012-12-28T01:38:44Z <p>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. </p> <p>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 <a href="http://ncatlab.org/nlab/show/smooth+algebra" rel="nofollow">smooth algebra</a>. </p> http://mathoverflow.net/questions/59939/identifying-poisoned-wines Identifying poisoned wines Qiaochu Yuan 2011-03-29T04:18:43Z 2012-12-27T04:20:14Z <p>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?</p> <p>It is not hard to see that the answer is $10$. Way back when math.SE first started, <a href="http://math.stackexchange.com/questions/639/logic-problem-identifying-poisoned-wines-out-of-a-sample-minimizing-test-subjec" rel="nofollow">a generalization</a> 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.</p> <p>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. </p> http://mathoverflow.net/questions/116749/spectra-of-elements-of-a-banach-algebra-and-the-role-played-by-the-hahn-banach-th/116750#116750 Answer by Qiaochu Yuan for Spectra of elements of a Banach algebra and the role played by the Hahn-Banach Theorem. Qiaochu Yuan 2012-12-19T03:15:20Z 2012-12-19T03:15:20Z <p>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... </p> <p>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 <a href="http://math.stackexchange.com/questions/157217/liouvilles-theorem-for-banach-spaces-without-the-hahn-banach-theorem" rel="nofollow">this math.SE question</a>). 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 <a href="http://math.stackexchange.com/questions/185305/is-the-fundamental-theorem-of-calculus-independent-of-zf" rel="nofollow">this math.SE question</a>. </p> http://mathoverflow.net/questions/116583/can-flt-fail-with-a-parametrization-over-some-extension-of-z/116589#116589 Answer by Qiaochu Yuan for Can FLT fail with a parametrization over some extension of Z? Qiaochu Yuan 2012-12-17T11:19:01Z 2012-12-17T11:19:01Z <p>No; in fact, you can take $K = \mathbb{C}$. This follows from the <a href="http://en.wikipedia.org/wiki/Mason%E2%80%93Stothers_theorem" rel="nofollow">Mason-Stothers theorem</a> in the same way that FLT for sufficiently large $n$ follows from the abc conjecture. </p> <p>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). </p> http://mathoverflow.net/questions/915/is-there-a-high-concept-explanation-for-why-characteristic-2-is-special Is there a high-concept explanation for why characteristic 2 is special? Qiaochu Yuan 2009-10-17T18:55:01Z 2012-12-11T00:08:34Z <p>The structure of the multiplicative groups of Z/pZ or of Z<sub>p</sub> 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.</p> <p>On the other hand, certain types of combinatorial questions can be reduced to linear algebra over F<sub>2</sub>, and this relationship doesn't seem to generalize to other finite fields. So in this example characteristic 2 is a nice special case.</p> <p>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.)</p> http://mathoverflow.net/questions/114738/integrating-powers-without-much-calculus/114739#114739 Answer by Qiaochu Yuan for Integrating Powers without much Calculus Qiaochu Yuan 2012-11-28T07:47:45Z 2012-11-29T06:57:14Z <p>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$.)</p> <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}$. </p> <p>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$... </p> http://mathoverflow.net/questions/114040/free-objects-in-functor-categories/114042#114042 Answer by Qiaochu Yuan for Free Objects in Functor Categories Qiaochu Yuan 2012-11-21T09:43:43Z 2012-11-21T09:54:44Z <p>$[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. </p> http://mathoverflow.net/questions/131255/objects-which-cant-be-defined-without-making-choices-but-which-end-up-independen/131278#131278 Comment by Qiaochu Yuan Qiaochu Yuan 2013-05-21T20:40:21Z 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. http://mathoverflow.net/questions/131364/how-much-of-character-theory-can-be-done-without-schurs-lemma-or-the-artin-wedde Comment by Qiaochu Yuan Qiaochu Yuan 2013-05-21T18:36:05Z 2013-05-21T18:36:05Z I think these &quot;ghost representations&quot; do exist; the literature on fusion categories might be a place to find them? http://mathoverflow.net/questions/131255/objects-which-cant-be-defined-without-making-choices-but-which-end-up-independen/131294#131294 Comment by Qiaochu Yuan Qiaochu Yuan 2013-05-21T04:05:02Z 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. http://mathoverflow.net/questions/131110/what-are-the-main-structure-theorems-on-finitely-generated-commutative-monoids Comment by Qiaochu Yuan Qiaochu Yuan 2013-05-19T05:53:57Z 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? http://mathoverflow.net/questions/130883/is-there-any-proof-that-you-feel-you-do-not-understand/130901#130901 Comment by Qiaochu Yuan Qiaochu Yuan 2013-05-17T18:28:46Z 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. http://mathoverflow.net/questions/130883/is-there-any-proof-that-you-feel-you-do-not-understand/130899#130899 Comment by Qiaochu Yuan Qiaochu Yuan 2013-05-17T04:30:31Z 2013-05-17T04:30:31Z Does this count as a proof at the undergraduate level? http://mathoverflow.net/questions/130883/is-there-any-proof-that-you-feel-you-do-not-understand/130901#130901 Comment by Qiaochu Yuan Qiaochu Yuan 2013-05-17T04:26:20Z 2013-05-17T04:26:20Z The recursion theorem ought to be a corollary of Lawvere's fixed point theorem, right? http://mathoverflow.net/questions/130749/reference-quote-request-all-of-combinatorics-is-the-representation-theory-of-s Comment by Qiaochu Yuan Qiaochu Yuan 2013-05-15T20:31:00Z 2013-05-15T20:31:00Z I think Igor Pak (?) once said something like &quot;gambling is the applied representation theory of the symmetric group,&quot; but I don't have a citation so I may have just imagined this. http://mathoverflow.net/questions/130422/strategic-vertex-labeling Comment by Qiaochu Yuan Qiaochu Yuan 2013-05-13T03:34:24Z 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. http://mathoverflow.net/questions/130319/show-that-this-ratio-of-factorials-is-always-an-integer Comment by Qiaochu Yuan Qiaochu Yuan 2013-05-11T07:01:50Z 2013-05-11T07:01:50Z @Tony: is it? That isn't clear to me. What embedding do you have in mind? http://mathoverflow.net/questions/104162/failure-of-a-basic-fact-from-representation-theory/104164#104164 Comment by Qiaochu Yuan Qiaochu Yuan 2013-05-07T02:43:10Z 2013-05-07T02:43:10Z @Yemon: yes, and I don't remember. I think parts of the argument come up in the McKay correspondence. http://mathoverflow.net/questions/129688/a-sufficient-condition-for-a-probability-measure-to-have-compact-support Comment by Qiaochu Yuan Qiaochu Yuan 2013-05-05T05:15:40Z 2013-05-05T05:15:40Z Perhaps <a href="http://en.wikipedia.org/wiki/Hausdorff_moment_problem" rel="nofollow">en.wikipedia.org/wiki/Hausdorff_moment_problem</a> is relevant? http://mathoverflow.net/questions/129359/boot-strapping-for-non-linear-functions Comment by Qiaochu Yuan Qiaochu Yuan 2013-05-01T23:34:01Z 2013-05-01T23:34:01Z This question belongs on <a href="http://stats.stackexchange.com/" rel="nofollow">stats.stackexchange.com</a> . http://mathoverflow.net/questions/128544/relationship-between-numerical-and-spectral-radii-for-product-of-positive-definit Comment by Qiaochu Yuan Qiaochu Yuan 2013-04-24T02:09:09Z 2013-04-24T02:09:09Z Oog, that's hard to read. Try $DAD$ instead? http://mathoverflow.net/questions/128564/can-inequivalent-topologies-have-same-sheaves-cohomology Comment by Qiaochu Yuan Qiaochu Yuan 2013-04-24T02:08:28Z 2013-04-24T02:08:28Z What do you mean by &quot;the same&quot; here? (There are two things this could mean, namely just isomorphic or literally the same sheaves.)