Slick ways to make annoying verifications - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T06:44:21Z http://mathoverflow.net/feeds/question/32968 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/32968/slick-ways-to-make-annoying-verifications Slick ways to make annoying verifications Charles Staats 2010-07-22T16:07:16Z 2012-10-29T21:33:26Z <p>There are many times in mathematics that one needs to make verifications that are annoying and distract from the main point of the argument. Often, there are lemmas that can make this much easier, at least in many important cases. </p> <p>For instance, in topology, it can be quite annoying to verify directly from the definition that a particular quotient space is what you think it is, and not something else with the same underlying set. (In fact, I suspect that many topologists habitually skip this verification.) However, the following lemma can in many cases make this verification much simpler:</p> <blockquote> <p><strong>Lemma:</strong> If $X$ is compact, $Y$ is Hausdorff, and $f \colon X \to Y$ is surjective, then $f$ is a quotient map.</p> </blockquote> <p>This lemma can be made more powerful using the fact that it suffices to show a map is locally a quotient map.</p> <p>Another such difficulty is to verify that a category is abelian; if you go directly from the definition, there is an annoyingly long list of things to verify. However, unless I am mistaken, once you have an abelian category $\mathcal{A}$, there are a number of other categories that are guaranteed to give other abelian categories. These (I think) include the category of functors into $\mathcal{A}$ from a fixed other category, the category of sheaves in $\mathcal{A}$ on a (topological space? other category?) (assuming $\mathcal{A}$ is nice enough for this to make sense), and any full subcategory of $\mathcal{A}$ that is closed under 0, $\oplus$, kernels, and cokernels. Using these in combination, together with the fact that $R$-mod is an abelian category for every ring $R$, I believe <strike>one can get to every abelian category used in Hartshorne</strike>. (Note: I am not too confident in this example, so if someone wanted to elaborate this in an answer, it would be appreciated.)</p> <p><em>EDIT:</em> As is pointed out in the comments below, the category of $\mathcal{O}_X$-modules is not of this form. (I came up with this example while writing the question, and did not think it through too carefully.) Thus, I would doubly appreciate a good answer specifically addressing, "How do you show a category is abelian?"</p> <blockquote> <p><strong>Question:</strong> What are some more of these useful lemmas / collections of lemmas, and how are they used?</p> </blockquote> http://mathoverflow.net/questions/32968/slick-ways-to-make-annoying-verifications/32971#32971 Answer by Daniel Litt for Slick ways to make annoying verifications Daniel Litt 2010-07-22T16:31:06Z 2012-10-22T23:29:36Z <ul> <li>The Yoneda Lemma (used everywhere!)</li> <li>In algebraic geometry, the vanishing locus of a map of vector bundles on a scheme $X$ is a closed subscheme of $X$.</li> </ul> <p>I'll give an example where we use both. Say we want to show that there is such a thing as a scheme of "flags" on a vector space $V$, and that it is a closed subscheme of projective space. Such a flag scheme $\text{Fl}_{i_1, ..., i_k}$ represents the functor sending a scheme $S$ to the set of $M_1\hookrightarrow ...\hookrightarrow M_k\hookrightarrow V\otimes \mathcal{O}_S$ where $M_j$ is a vector bundle on $S$ of rank $i_j$ and where all the maps are injective bundle maps. We could do this by working with coordinates, but that would be a huge pain, so let's use our lemmas.</p> <p>It suffices to do this for $k=2$, as larger flag schemes can be written as fiber products of $\text{Fl}_{i_1, i_2}$. We embed $\text{Fl}_{i_1, i_2}$ as a closed subscheme of the scheme $T:=\text{Gr}(i_1, V)\times \text{Gr}(i_2, V)$. We know that this is a closed subscheme of $\mathbb{P}(\Lambda^{i_1}(V)\otimes \Lambda^{i_2}(V))$ so this suffices.</p> <p>But indeed, letting $M_j$ be the canonical rank $i_j$ bundle over $\text{Gr}(i_j, V)$ (induced by the identity map through the universal property of the Grassmannian and Yoneda), we have that the flag bundle $\text{Fl}_{i_1, i_2}$ is the vanishing locus of the map $p_1^*M_1\to \text{coker}(p_2^*M_2\to V\otimes \mathcal{O}_T)$. It's easy to check that this represents the desired functor.</p> http://mathoverflow.net/questions/32968/slick-ways-to-make-annoying-verifications/32984#32984 Answer by Nate Eldredge for Slick ways to make annoying verifications Nate Eldredge 2010-07-22T17:57:29Z 2010-07-22T17:57:29Z <p>In functional analysis, the <strong>closed graph theorem </strong> is a good example of this. If you have two Banach spaces $X,Y$ and you define some linear operator $A : X \to Y$ on all of $X$, you often need to verify that it is continuous. Naively you would say, "let $x_n$ be a sequence in $X$ converging to some $x$; I have to show (1) that $A x_n$ converges and (2) its limit is $Ax$." But the closed graph theorem asserts that any everywhere defined operator between Banach spaces with a closed graph is in fact continuous. An operator has a closed graph iff for any sequence $x_n$ in $X$ such that $x_n$ <em>and</em> $A x_n$ converge, one has $\lim A x_n = A \lim x_n$. So in the argument above, you can skip the verification of (1) and treat it instead as an assumption.</p> <p>There is also the closely related open mapping theorem, which says that a continuous linear bijection $B : X \to Y$ of Banach spaces is automatically a homeomorphism; i.e. you get to skip the verification that $B^{-1}$ is continuous. It's reminiscent of the theorem that any continuous bijection $f : K_1 \to K_2$ of compact Hausdorff spaces is automatically a homeomorphism.</p> http://mathoverflow.net/questions/32968/slick-ways-to-make-annoying-verifications/32994#32994 Answer by muad for Slick ways to make annoying verifications muad 2010-07-22T19:17:44Z 2010-07-22T19:17:44Z <p>My example is perhaps not exactly what you had in mind, but I hope that will make it more interesting, thus my reason for posting it. I thought of mentioning the (very elementary) but delightfully clever method of proving polynomials equal by comparing them evaluated at finitely many points (which is applied in, for example in <a href="http://www.jstor.org/pss/2690530" rel="nofollow">A Proof in the Spirit of Zeilberger of an Amazing Identity of Ramanujan</a>) but instead I thought I would point out the notion of reflective proof from dependent type theory:</p> <p>To write a formal (computer checkable proof) you must justify every single step of reasoning all the way down to the axioms of the foundation. Of course that would make proving simple things like $((ab)cd)e = a(bc)(de)$ a terrible chore requiring repeated applications of the associativity (infact proving something as simple as $1 + 100 = 101$ could require $100$ applications of the definition of plus!). The idea of reflection is to reduce trivial reasoning steps to computation, This is described in Section 4 of Henk Barendregt's <a href="ftp://ftp.cs.kun.nl/pub/CompMath.Found/wiley.pdf" rel="nofollow">Proofs of correctness in Mathematics and Industry</a>, but it was also applied heavily in a recent <a href="http://research.microsoft.com/en-us/people/gonthier/4colproof.pdf" rel="nofollow">formal proof of the four color theorem</a>.</p> http://mathoverflow.net/questions/32968/slick-ways-to-make-annoying-verifications/33054#33054 Answer by Dylan Wilson for Slick ways to make annoying verifications Dylan Wilson 2010-07-23T06:23:31Z 2012-10-23T18:47:42Z <p>Riffing off of Nate's answer, another result in functional analysis (often proven in the same breath as the others) is the Uniform Boundedness Principle. This is exceedingly useful in getting uniform estimates from pointwise ones... and it's pretty magical. It says that if we have a collection $\mathcal{F}$ of continuous linear operators from a Banach space to a normed vector space, then these are uniformly bounded (i.e. $\sup_{T \in \mathcal{F}} \Vert T \Vert &lt; \infty$) if they are pointwise bounded (i.e., for every $x$ we have $\sup_{T \in\mathcal{F}} \Vert T(x)\Vert &lt; \infty$). </p> http://mathoverflow.net/questions/32968/slick-ways-to-make-annoying-verifications/33098#33098 Answer by gowers for Slick ways to make annoying verifications gowers 2010-07-23T15:20:13Z 2010-07-23T15:20:13Z <p>Sometimes in elementary analysis there are things that are a pain to check, but one can at least minimize the pain. For example, if you want to prove that for every &delta;&gt;0 the sequence $(1+&delta;)^n$ is unbounded, you can use the lemma that it is at least 1+n&delta;, and more generally if you want to prove that it grows faster than any power you can use the lemma that it is at least $\binom nk&delta;^k$, both of which follow from the binomial expansion.</p> <p>Another one I like from elementary analysis. Suppose you want to prove rigorously that cos(x) is always at least $1-x^2/2$. You can do it as follows. First, cos(x) is always at most 1. It follows by integrating that sin(x) is at most x when x is positive. And then by integrating again we get the result for positive x, and evenness does the rest. (The integral shows that -cos(x)+cos(0) is always at most $x^2/2$, and rearranging proves the inequality.) Iterating this argument gives you the inequality you expect wherever you truncate the Taylor expansion. </p> http://mathoverflow.net/questions/32968/slick-ways-to-make-annoying-verifications/33377#33377 Answer by gowers for Slick ways to make annoying verifications gowers 2010-07-26T09:26:05Z 2010-07-26T09:26:05Z <p>The probabilistic method is a good source of slick proofs of things that are either very hard to prove or even not known to be provable in any other way. For example, suppose you are asked to prove that it is possible to find infinitely many points in general position on the unit sphere in R^d. If you take any d-1 points, then the probability that a random point lies in the subspace they generate is zero. So if you randomly pick an infinite sequence of points, then the probability that it fails to be an example is zero. Actually thinking up an example and proving that it worked would be pretty tedious.</p> http://mathoverflow.net/questions/32968/slick-ways-to-make-annoying-verifications/33435#33435 Answer by Bill Dubuque for Slick ways to make annoying verifications Bill Dubuque 2010-07-26T19:35:36Z 2010-07-26T19:35:36Z <p>Proofs exploiting universality often provide nice examples of slick ways to avoid annoying special cases. For example, the matrix identities below have trivial algebraic proofs by proceeding "generically", i.e. let the matrix entries $a_{ij}, b_{ij}$ be indeterminates and perform the proof over the polynomial ring $\mathbb Z[a_{ij}, b_{ij}]$. </p> <p>$\rm\quad\; det(I-AB) = det(I-BA)\;\:$ by taking $\;\rm det\;$ of $\;\;\rm (I-AB)\;A = A\;(I-BA)\;$ then canceling $\;\rm det \:A$</p> <p>$\rm\quad\quad det(adj \:A) = (det \:A)^{n-1}\quad$ by taking $\;\rm det\;$ of $\;\rm\quad A\;(adj\: A) = (det\: A) \;I\quad\;\;$ then canceling $\;\rm det \:A$</p> <p>Contrast these absolutely trivial <em>algebraic</em> proofs with the more complex and more frequently presented <em>topological</em> proofs via density arguments. See my <a href="http://mathoverflow.net/questions/32133/expressing-adja-as-a-polynomial-in-a/32343#32343" rel="nofollow">post [1]</a> and its comments for some further discussion.</p> http://mathoverflow.net/questions/32968/slick-ways-to-make-annoying-verifications/34690#34690 Answer by Anweshi for Slick ways to make annoying verifications Anweshi 2010-08-05T21:32:16Z 2010-08-05T21:32:16Z <p>Before algebraic geometry was developed sufficiently and the Riemann-Roch was proved with its present power, the <a href="http://en.wikipedia.org/wiki/Algebraic_geometry_and_analytic_geometry%23The_Lefschetz_principle" rel="nofollow">Lefschetz principle</a> was used to dispose of many statements in algebraic geometry.</p> <p>For instance: Define an elliptic curve over a field as a curve in the Weierstrass form with nonzero determinant. Upon this define the addition and inverse laws using the chord-and-tangent process, obtaining algebraic expressions. To show that the elliptic curve is a group, you have to show the addition is associative. One way is a very tedious verification of the identities. </p> <p>Another way is to use elliptic functions to prove the identity in the complex case. Since the algebraic group law holds true over the complex numbers, it is satisfied by an infinite number of algebraically independent solutions, and therefore the group law must be true in universality, over any field whatsoever. Of course this needs to be made precise with Lefschetz principle.</p> <p>But later algebraic geometry developed and it was possible to prove statements without relying on the Lefschetz principle. For instance, the group law on elliptic curve is always a consequence of the Riemann-Roch.</p> http://mathoverflow.net/questions/32968/slick-ways-to-make-annoying-verifications/49105#49105 Answer by Terry Tao for Slick ways to make annoying verifications Terry Tao 2010-12-12T00:21:32Z 2010-12-12T00:21:32Z <p>One can often work out the exponents in some identity or inequality by using dimensional analysis or by plugging in key examples, and this is often faster than deriving the identity or inequality painstakingly by hand. I discuss this in more detail at</p> <p><a href="http://terrytao.wordpress.com/2008/12/27/tricks-wiki-use-basic-examples-to-calibrate-exponents/" rel="nofollow">http://terrytao.wordpress.com/2008/12/27/tricks-wiki-use-basic-examples-to-calibrate-exponents/</a></p> http://mathoverflow.net/questions/32968/slick-ways-to-make-annoying-verifications/49119#49119 Answer by Rbega for Slick ways to make annoying verifications Rbega 2010-12-12T05:04:43Z 2010-12-12T05:04:43Z <p>How about this (presumably) common practice:</p> <p>Suppose $f:M\to \mathbb{R}$ a smooth function from some manifold $M$ (that maybe has extra structure $S$) and you are trying to prove some property $P$ (about $M$, $S$ or $f$). Suppose also that your life would be much easier if you could assume that $f$ was Morse. </p> <p>You are often saved from much tedium by (hopefully) finding that your result is generic". That is:</p> <p>1) There is a family of smooth functions $f_\epsilon:M\to \mathbb{R}$ with $f_0=f$ and for $\epsilon>0$ $f_\epsilon$ is Morse. </p> <p>2) You can then easily prove some properties $P_\epsilon$ (modulo adjusting your structure to $S_\epsilon$) about ($M$, $S_\epsilon$ or $f_\epsilon$) that have the additional property of implying $P$ "by letting $\epsilon\to 0$".</p> <p>Of course there are always those times (and I speak from personal experience) where things are too special" for such an approach to work. Then you have to get your hands dirty. </p> http://mathoverflow.net/questions/32968/slick-ways-to-make-annoying-verifications/49124#49124 Answer by Adam Hughes for Slick ways to make annoying verifications Adam Hughes 2010-12-12T06:25:45Z 2012-10-29T21:33:26Z <p>My example comes from algebraic geometry, specifically in the theory of $\lambda$-rings, which are used in K-theory and representation theory (and possibly other places of which I am unaware). If you look in <em>Lecture Notes in Mathematics</em> 308 <em>$\lambda$-rings and the Reprsentation Theory of the Symmetric Group</em> by Donald Knutson, on pp 27, there is a theorem which is called--quite appropriately--the "Verification Principle", and it is used to do exactly the kind of thing you're asking about. The statement is:</p> <p>If $\mu$ is a $\lambda$-ring operation, then $\mu$ is uniquely a polynomial in the $\lambda$-operations and for any particular polynomial $f(\lambda^1,\lambda^2,\ldots , \lambda^n,\ldots)$ it is sufficient to check that $\mu = f$, operating on a sum $\xi_1+\ldots + \xi_r$ of elements of degree 1, for all $r>0$. If you read the first part of the book (i.e. up to page 27 where you read this) you learn that this is a very handy thing indeed, especially given the generating function polynomials that show up in the study of these objects and how much easier it is to check for things which are polynomials in the $\lambda$-operations (as they are called). It is this that so nicely ties this kind of ring in with the representation theory of the symmetric group, in particular the elementary symmetric functions, as Knutson mentions on p. 10 of the same publication.</p> <p>Another useful technique is one that comes up in algebra, when you check something for general elements by checking on a basis. Eg. testing something for all the elements of your tensor or exterior algebra by testing it on the "pure" or "completely decomposable" tensors which form a generating set.</p> http://mathoverflow.net/questions/32968/slick-ways-to-make-annoying-verifications/110416#110416 Answer by Michael Murray for Slick ways to make annoying verifications Michael Murray 2012-10-23T10:56:11Z 2012-10-23T23:40:31Z <p>Elementary but still useful is the regular value theorem or the submersion theorem:</p> <p>Let $f \colon M \to N$ be smooth and $n \in N$. If $T(f)_m \colon T_m M \to T_{f(m)} N$ is onto for all $m \in f^{-1}(n)$ then $f^{-1}(n) \subset M$ is a submanifold of dimension $\text{dim}(N) - \text{dim}(M)$. </p> http://mathoverflow.net/questions/32968/slick-ways-to-make-annoying-verifications/110426#110426 Answer by Igor Khavkine for Slick ways to make annoying verifications Igor Khavkine 2012-10-23T12:04:21Z 2012-10-23T12:04:21Z <p>To show that $E\to M$ is a $G$-bundle (say in the fin-dim manifold category), one needs to check local triviality using some charts on $M$ and $E$ and that transitions between them are controlled by the group $G$. However, if you have a principal $G$-bundle on your hands, you can easily use the associated bundle construction to build the total space and the projection maps that satisfy the bundle property given only how $G$ acts on an abstract typical fiber.</p> http://mathoverflow.net/questions/32968/slick-ways-to-make-annoying-verifications/110445#110445 Answer by Thomas Richard for Slick ways to make annoying verifications Thomas Richard 2012-10-23T16:38:46Z 2012-10-23T19:26:25Z <p>A really elementary one :</p> <p>A linear map between two vector spaces of the same finite dimension is an isomorphism if and only if its kernel is zero.</p> <p>As an application, I like the proof of the existence of Lagrange interpolation polynomials.</p> http://mathoverflow.net/questions/32968/slick-ways-to-make-annoying-verifications/110451#110451 Answer by Laurent Berger for Slick ways to make annoying verifications Laurent Berger 2012-10-23T17:33:22Z 2012-10-23T17:33:22Z <p>A surjective map between two modules (over a commutative ring) of the same rank is a bijection.</p> http://mathoverflow.net/questions/32968/slick-ways-to-make-annoying-verifications/110452#110452 Answer by RenĂ© Pannekoek for Slick ways to make annoying verifications RenĂ© Pannekoek 2012-10-23T17:57:37Z 2012-10-23T17:57:37Z <p>A group homomorphism from a topologically finitely generated profinite group to any profinite group is continuous. (Nikolov-Segal, arxiv:math/0604399v1)</p> http://mathoverflow.net/questions/32968/slick-ways-to-make-annoying-verifications/110458#110458 Answer by Dylan Wilson for Slick ways to make annoying verifications Dylan Wilson 2012-10-23T18:52:51Z 2012-10-23T18:52:51Z <p><strong>To show that an object S has property P, first show that the collection of all objects satisfying P is closed under a bunch of operations, prove that certain very simple objects have property P, and show that S can be "decomposed" or "filtered" or somehow unscrewed into these simple objects using the operations mentioned above.</strong></p> <p>This is a sort of induction, and it is used all the time to turn annoying verifications into verifying that something is true for like... a point. Maybe a shorthand for this "slick method" would be "think like Grothendieck."</p> <p>For lots of examples of this see any proof in Higher Topos Theory or Higher Algebra by Lurie.</p>