On proving that a certain set is not empty by proving that it is actually large - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T06:59:47Z http://mathoverflow.net/feeds/question/34390 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/34390/on-proving-that-a-certain-set-is-not-empty-by-proving-that-it-is-actually-large On proving that a certain set is not empty by proving that it is actually large Malik Younsi 2010-08-03T14:32:24Z 2010-08-04T11:42:31Z <p>It happens occasionally that one can prove that a given set is not empty by proving that it is actually large. The word "large" here may refer to different properties.</p> <p>For example, one can prove that a certain set is not empty by proving that its cardinality is big, as in the proof that there exist transcendental numbers : The set of algebraic numbers is countable, but the set of real numbers is uncountable, so there is uncountably many transcendental numbers.</p> <p>One could also prove that a certain set is not empty by proving, for example, that it has positive measure, that it is dense, etc.</p> <p>What are some good examples of such proofs?</p> http://mathoverflow.net/questions/34390/on-proving-that-a-certain-set-is-not-empty-by-proving-that-it-is-actually-large/34392#34392 Answer by Anweshi for On proving that a certain set is not empty by proving that it is actually large Anweshi 2010-08-03T14:41:33Z 2010-08-03T15:25:15Z <p>There are non-Borel sets that are Lebesgue measurable. This is proved in the following way. First show that the Borel sigma algebra for the real line is uncountable with cardinality of the real line. On the other hand, you have the Cantor set which is uncountable(cardinality = $\mathbb R$) and is of Lebesgue measure zero. Since Lebesgue measure is complete, every subset of the Cantor set belongs to the Lebesgue sigma algebra and therefore the Lebesgue sigma algebra has cardinality of the power set of the reals. </p> <p>Construction of explicit examples <a href="http://mathoverflow.net/questions/32720/non-borel-sets-without-axiom-of-choice" rel="nofollow">would require</a> axiom of choice.</p> http://mathoverflow.net/questions/34390/on-proving-that-a-certain-set-is-not-empty-by-proving-that-it-is-actually-large/34393#34393 Answer by Petya for On proving that a certain set is not empty by proving that it is actually large Petya 2010-08-03T14:42:10Z 2010-08-03T14:42:10Z <p>Sard's lemma is an example - the set of regular values is non-empty since it has positive measure.</p> <p>The following example also answers your question: Recently I proved the following lemma. </p> <p>Let $f\colon M\to N$ be a smooth map, $M$ is a non-empty paracompact manifold. Let $k$ be a maximal rank of a differential $df(x)$ over $x\in M$. Then there exists a point $y$ in $f(M)$ such that the rank of the differential $df$ is maximal for all points of $f^{-1}(y)$. </p> http://mathoverflow.net/questions/34390/on-proving-that-a-certain-set-is-not-empty-by-proving-that-it-is-actually-large/34396#34396 Answer by Andrey Rekalo for On proving that a certain set is not empty by proving that it is actually large Andrey Rekalo 2010-08-03T14:48:53Z 2010-08-03T15:32:32Z <p>Many existence proofs which exploit the idea of Baire category. </p> <p>For instance, existence of a metrically transitive automorphism of the closed unit square was first obtained by the category method (see <a href="http://www.ams.org/mathscinet/search/publdoc.html?arg3=&amp;co4=AND&amp;co5=AND&amp;co6=AND&amp;co7=AND&amp;dr=all&amp;pg4=AUCN&amp;pg5=TI&amp;pg6=PC&amp;pg7=ALLF&amp;pg8=ET&amp;r=1&amp;review_format=html&amp;s4=oxtoby&amp;s5=metrical%2520transitivity&amp;s6=&amp;s7=&amp;s8=All&amp;vfpref=html&amp;yearRangeFirst=&amp;yearRangeSecond=&amp;yrop=eq" rel="nofollow">"Measure-preserving homeomorphisms and metrical transitivity"</a> by Oxtoby and Ulam) . Another classical example is due to Banach who proved that every function from a residual subset of $C[0,1]$ is nowhere differentiable.</p> <p>A nice and elementary <a href="http://books.google.co.uk/books?id=wUDjoT5xIFAC&amp;pg=PR7&amp;lpg=PR7&amp;dq=measure+and+category&amp;source=bl&amp;ots=4EMy1X1RUN&amp;sig=cd5KeoXCfve3gNwvk2wyrOmTLmU&amp;hl=en&amp;ei=VS5YTIfsH9GT4gaesIj_Bg&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=5&amp;ved=0CDIQ6AEwBA#v=onepage&amp;q&amp;f=false" rel="nofollow">book</a> by Oxtoby discusses these and many other applications of the category method.</p> http://mathoverflow.net/questions/34390/on-proving-that-a-certain-set-is-not-empty-by-proving-that-it-is-actually-large/34401#34401 Answer by Matt Young for On proving that a certain set is not empty by proving that it is actually large Matt Young 2010-08-03T15:18:59Z 2010-08-03T15:18:59Z <p>Virtually any existence proof in analytic number theory goes by giving a quantitative lower bound (or asymptotic formula) for the number of objects of interest. For example, there are infinitely many primes of the form $x^2 + y^4$ was shown by Friedlander and Iwaniec by finding an asymptotic formula for the counting function of such primes.</p> <p>When I was in graduate school, a paper appeared on the arxiv purporting to prove the twin prime conjecture by establishing an asymptotic formula for the number of twin primes up to $x$. I remarked to my advisor, Iwaniec, that surely there was a mistake since the conclusion was so strong. He responded by saying that giving the asymptotic formula was actually a good sign. (It should go without saying that there was a mistake in the paper).</p> http://mathoverflow.net/questions/34390/on-proving-that-a-certain-set-is-not-empty-by-proving-that-it-is-actually-large/34403#34403 Answer by Francesco Polizzi for On proving that a certain set is not empty by proving that it is actually large Francesco Polizzi 2010-08-03T15:28:12Z 2010-08-04T08:08:40Z <p>A kind of analogue of Sard's Lemma in Algebraic Geometry is Bertini's Theorem:</p> <p>"Given a linear sistem $|L|$ on a smooth projective variety X, its general element is smooth outside the base points".</p> <p>In particular, if $|L|$ is base-point free then the set of smooth elements in $|L|$ is dense, in particular non-empty. </p> http://mathoverflow.net/questions/34390/on-proving-that-a-certain-set-is-not-empty-by-proving-that-it-is-actually-large/34404#34404 Answer by Andrea Ferretti for On proving that a certain set is not empty by proving that it is actually large Andrea Ferretti 2010-08-03T15:28:33Z 2010-08-03T15:28:33Z <p><a href="http://www.tricki.org/article/Cardinality_measure_and_category" rel="nofollow">This page</a> of the Tricki describes exactly the technique you are looking for.</p> http://mathoverflow.net/questions/34390/on-proving-that-a-certain-set-is-not-empty-by-proving-that-it-is-actually-large/34405#34405 Answer by Emerton for On proving that a certain set is not empty by proving that it is actually large Emerton 2010-08-03T15:32:21Z 2010-08-03T15:32:21Z <p>Frequently in arguments in algebraic number theory, one has to choose a prime that satisfies some list of conditions, and is bigger than some given bound. (A simple example of the kind of condition that I am thinking of would be that the prime should lie in a given congruence class modulo some number $n$.) One then interprets the conditions in such a way as to be able to apply the Cebotarev density theorem to conclude that there are infinitely many primes satisfying the given conditions, and so in particular a suitable prime can be found that lies above the desired bound. (In the simple example, one would use Dirichlet's theorem on the existence of infinitely many primes in arithmetic progression, which from this point of view is a special case of Cebotarev density.)</p> http://mathoverflow.net/questions/34390/on-proving-that-a-certain-set-is-not-empty-by-proving-that-it-is-actually-large/34408#34408 Answer by Olivier for On proving that a certain set is not empty by proving that it is actually large Olivier 2010-08-03T16:08:55Z 2010-08-03T16:08:55Z <p>C.Cornut and V.Vatsal's proof (as in e.g Inventiones mathematicae 148) of the non-triviality of CM points on zero and one-dimensional quaternionic Shimura varieties as one goes up an anticylcotomic $\mathbb Z_{p}$-extension $K_{\infty}$ is by showing that reduction modulo $\ell$ of CM points is actually onto points modulo $\ell$ for infinitely many $\ell$. In particular, their proof actually implies the much stronger statement that the $\mathbb Z_{p}[[\Gamma]]$-module generated by the image of the norm-coherent CM points under the Kummer map has trivial $\mu$-invariant (here $\Gamma$ is the Galois group of $K_{\infty}/K$). </p> http://mathoverflow.net/questions/34390/on-proving-that-a-certain-set-is-not-empty-by-proving-that-it-is-actually-large/34410#34410 Answer by Roland Bacher for On proving that a certain set is not empty by proving that it is actually large Roland Bacher 2010-08-03T16:39:24Z 2010-08-03T18:36:55Z <p>Not quite an answer to the question but related (large modulo $2$):</p> <p>Zagier's beautiful proof (Amer. Math. Monthly 97 (1990), no. 2, 144) that every prime congruent to $1$ modulo $4$ is a sum of two squares is based on the fact that the cardinality of a certain finite set is odd and the set is thus non-empty.</p> http://mathoverflow.net/questions/34390/on-proving-that-a-certain-set-is-not-empty-by-proving-that-it-is-actually-large/34450#34450 Answer by Stefan Geschke for On proving that a certain set is not empty by proving that it is actually large Stefan Geschke 2010-08-03T23:14:02Z 2010-08-03T23:14:02Z <p>I just heard this in a talk by Jan Krajicek: It is known that there are Boolean functions that require a "large" circuit to compute them, but the proof is probabilistic. (I.e., the measure of the set of such Boolean function (say of arity n) is known to be nonzero.) No explicit construction of such functions is known.</p> http://mathoverflow.net/questions/34390/on-proving-that-a-certain-set-is-not-empty-by-proving-that-it-is-actually-large/34485#34485 Answer by Douglas Zare for On proving that a certain set is not empty by proving that it is actually large Douglas Zare 2010-08-04T07:58:39Z 2010-08-04T07:58:39Z <p>As Tsuyoshi Ito commented, the <a href="http://en.wikipedia.org/wiki/Probabilistic_method" rel="nofollow">probabilistic method</a> in combinatorics is an example. You use a probability measure on the space of possibilities, and show that the set with the desired probabilities has positive measure, hence is nonempty. </p> <p>The classic example of this is the result by Erdős (1947) that the Ramsey number $R(t,t)$ grows at least exponentially with $t$. If you consider a random coloring of the edges of the complete graph on $n$ vertices, then the probability that a particular complete subgraph on $t$ vertices is monochromatic is $2^{1-{t \choose 2}}$. If ${n\choose t} 2^{1-{t \choose 2}} \lt 1$, then a random coloring has no monochromatic subgraph with positive probability. This is the case for $n = \sqrt 2^t$, $t\gt 2$, so $R(t,t) \ge \sqrt2^t$ for $t \gt 2$. </p> <p>For slightly smaller $n$, most random colorings of the complete graph on $n$ vertices have no monochromatic subgraph of size $t$, but finding a construction has been an open problem. </p> http://mathoverflow.net/questions/34390/on-proving-that-a-certain-set-is-not-empty-by-proving-that-it-is-actually-large/34494#34494 Answer by Mark Schwarzmann for On proving that a certain set is not empty by proving that it is actually large Mark Schwarzmann 2010-08-04T11:42:31Z 2010-08-04T11:42:31Z <p>The theme is prevalent in combinatorial number theory and ergodic theory. Consider the ergodic Szemerédi theorem, for instance. It says that if $(X,\mathcal{B},\mu,T)$ is a measure-preserving system and $A \in \mathcal{B}$ has $\mu (A) >0$, then $\forall k \in \mathbb{N}$ $\exists n \in \mathbb{N}$ so that $\mu (A \cap T^{-n}A \cap T^{-2n}A \cap \cdots \cap T^{-kn}A)>0$. It turns out that it's easier to prove that measure of the intersection is positive for infinitely many $n$. In fact, Furstenberg's original proof showed that $\liminf_{N \to \infty} \frac{1}{N} \sum_{n=1}^{N} \mu (A \cap T^{-n}A \cap T^{-2n}A \cap \cdots \cap T^{-kn}A) > 0$.</p>