Are some numbers more irrational than others? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T05:07:57Z http://mathoverflow.net/feeds/question/53724 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/53724/are-some-numbers-more-irrational-than-others Are some numbers more irrational than others? I. J. Kennedy 2011-01-29T16:11:17Z 2011-02-05T15:14:37Z <p>Some irrational numbers are transcendental, which makes them in some sense "more irrational" than algebraic numbers. There are also numbers, such as the golden ratio $\varphi$, which are poorly approximable by rationals. But I wonder if there is another sense in which one number is more irrational than another.</p> <p>Consider the following well known irrationals: $\sqrt{2}$, $\varphi$, $\log_2{3}$, $e$, $\pi$, $\zeta(3)$.</p> <p>The proofs of irrationality of these numbers increase in difficulty from grade-school arguments, to calculus, to advanced methods. Other probable irrationals such as $\gamma$ most likely have very difficult proofs.</p> <p>Can this notion be made precise? Is there a well defined way in which, for example, $\pi$ is more irrational than $e?$</p> http://mathoverflow.net/questions/53724/are-some-numbers-more-irrational-than-others/53725#53725 Answer by Zev Chonoles for Are some numbers more irrational than others? Zev Chonoles 2011-01-29T16:18:24Z 2011-01-30T00:19:14Z <p>Yes, there is such a thing as the <a href="http://en.wikipedia.org/wiki/Liouville_number#Irrationality_measure" rel="nofollow"><strong>irrationality measure</strong></a> of a real number (I'm not sure if it can be / has already been extended to complex numbers). It is based on the idea that all algebraic numbers (including the golden ratio) are hard to approximate well by rationals, relative to the size of the denominator of the rational used, while it is sometimes possible for a transcendental number to be approximated better. In particular, if a number $\alpha\in\mathbb{R}\setminus\mathbb{Q}$ has the property that there are infinitely many rational approximations $\frac{p}{q}\in\mathbb{Q}$ with $|\,\alpha-\frac{p}{q}|&lt; q^{-t}$, then $t$ is a lower bound for the irrationality measure of $\alpha$; the larger $t$ is, i.e. the better your approximations are relative to the denominator, the "more irrational" you are, at least from a Diophantine approximation point of view.</p> <p>From Wikipedia: The irrationality measure of a rational number is 1; the very deep <a href="http://en.wikipedia.org/wiki/Thue%E2%80%93Siegel%E2%80%93Roth_theorem" rel="nofollow">theorem</a> of Thue, Siegel, and Roth shows that any algebraic number that isn't rational has irrationality measure 2; and transcendental numbers will have an irrationality measure $\geq2$. However, as Douglas Zare has pointed out in the comments, the set of transcendental numbers of irrationality measure $>2$ has measure 0, so that in most cases it's unfortunately not useful as a comparison.</p> <p>It appears that the irrationality measure of $\pi$ is not currently known, but that there are upper bounds; the most recent one I could find is <a href="http://iopscience.iop.org/0036-0279/63/3/L11/pdf/RMS_63_3_L11.pdf" rel="nofollow">this</a>, which would appear to show that $\mu(\pi)\leq7.6063$. The Wikipedia article claims that $\mu(e)=2$, so whether or not $\pi$ is "more irrational" than $e$ looks like an open question.</p> http://mathoverflow.net/questions/53724/are-some-numbers-more-irrational-than-others/53726#53726 Answer by Mark Sapir for Are some numbers more irrational than others? Mark Sapir 2011-01-29T16:38:14Z 2011-01-29T16:38:14Z <p>In principle, yes, you can measure irrationality of a number by the length of a shortest formal proof (in some formal proof system), something like the <a href="http://en.wikipedia.org/wiki/Kolmogorov_complexity" rel="nofollow">Kolmogorov complexity</a> of a sequence. But it is difficult (if at all possible) to compute and the usefulness of it is not clear. </p> http://mathoverflow.net/questions/53724/are-some-numbers-more-irrational-than-others/53745#53745 Answer by Gerry Myerson for Are some numbers more irrational than others? Gerry Myerson 2011-01-29T22:53:15Z 2011-01-29T22:53:15Z <p>I agree with Mark Sapir's comments on shortest formal proofs. Also, Douglas Zare is correct to point out the difficulties of using irrationality measure. A refinement of irrationality measure was proposed by Mahler many years ago. It's rather technical, and instead of presenting the details here I suggest you type the words "Mahler" and "classification" into a search engine and peruse the many items your search will turn up. </p> <p>Mahler's classification, like the irrationality measure, suffers from the difficulty of actually calculating which class any given number falls in. </p> http://mathoverflow.net/questions/53724/are-some-numbers-more-irrational-than-others/53750#53750 Answer by quid for Are some numbers more irrational than others? quid 2011-01-30T00:09:44Z 2011-01-30T00:09:44Z <p>For algebraic numbers one could take as a simple measure the degree of the number (lowest degree of non-zero rational polynomial having the number as a zero).</p> <p>Of course, degree one are the rationals. And, degree two (quadratic irrationalities) have for example a nice characterization via being precisely those numbers with infinite yet periodic continued fraction expansion.</p> <p>Though, others have already commented regarding classification by length/complexity proof and its problems, I wanted to add a (somewhat naive and subjective) remark:</p> <p>I take the question as seeking (at least partially) some notion that matches (to a certain extent) an intuitive idea of what is more or less irrational. However, if this is so, then at least for my intuition (of course this being subjective), this would not work well at all, as there are quite different reasons why there is a simple/short proof of irrationality.</p> <p>For example, comparing the perhaps two simplest arguments for irrationality: .) the irrationality of roots of integers (other then perfect powers) .) the irrationality of a number given by a description of its decimal expansion (provided it can be easily seen to be non-periodic) </p> <p>The former yields only irrational numbers that I consider as very nice and not 'strange' at all.</p> <p>Yet, using the latter one can get numbers that I consider as rather 'strange' (The obviously irrational number with decimal-expansion all 0 except at prime-place where the digit is 1, and at prime-power places where the digit is 7, has no intuitive meaning for me at all.)</p> <p>So, a classification that puts those two types close together is not intuitive to me. </p> http://mathoverflow.net/questions/53724/are-some-numbers-more-irrational-than-others/53754#53754 Answer by Joel David Hamkins for Are some numbers more irrational than others? Joel David Hamkins 2011-01-30T01:49:07Z 2011-01-30T01:54:12Z <p>The other answers and comments are fascinating, particularly about the irrationality measure, but allow me to give a little more information along the lines of Mark Sapir's answer by mentioning that there are several very large, intensely studied hierarchies of complexity for reals numbers. After the initial familiar notions come several others...</p> <ul> <li><p>rational</p></li> <li><p>algebraic</p></li> <li><p>computable</p></li> </ul> <p>The computable reals are those for which we can compute rational approximations to any desired accuracy, by Turing machine. (A concept used in <a href="http://en.wikipedia.org/wiki/Computable_analysis" rel="nofollow">computable analysis</a>.) The computable subsets of $\mathbb{N}$ are those for which we can compute <em>yes/no</em> answers for membership in finite time. For example, all the numbers you mention in the question, such as $\pi$ and $e$, are computable.</p> <ul> <li>computably enumerable</li> </ul> <p>The c.e. subsets of $\mathbb{N}$ are those for which there is a computable enumeration procedure. Equivalently, you can compute the <em>yes</em> answers for membership in finite time. The concept of relative (oracle) computability leads to the <a href="http://en.wikipedia.org/wiki/Turing_degrees" rel="nofollow">hierarchy of Turing degrees</a>, which measures the comparative computable complexity of a real.</p> <ul> <li>arithmetic</li> </ul> <p>A real $x$ is <em>arithmetic</em> if it's digits can be defined by a definition involving only quantification over the natural numbers and primitive operations. Equivalently, the arithmetic subsets of $\mathbb{N}$ arise from the computable subsets of $\mathbb{N}^k$ by projection and complement. The <a href="http://en.wikipedia.org/wiki/Arithmetic_hierarchy" rel="nofollow">arithmetic hierarchy</a> breaks naturally into levels, such as $\Sigma^0_n$ and $\Pi^0_n$, corresponding to the logical complexity of these definitions, and these levels are refined by the Turing degrees. For example, the set of Turing machine programs $p$ which compute total functions forms a complete $\Pi^0_2$ set. The relativized notion leads to the arithmetic degrees.</p> <ul> <li>hyperarithmetic</li> </ul> <p>A real is <em>hyperarithmetic</em> if it can be defined by two equivalent definitions, one involving just one universal quantifier over the reals and another having just one existential quantifier over the reals, and otherwise any level of arithmetic quantifiers. This is the same as $\Delta^1_1$. The <a href="http://en.wikipedia.org/wiki/Hyperarithmetical_theory" rel="nofollow">hyperarithmetic hierarchy</a> is stratified in a hierarchy of length $\omega_1^{CK}$, a lightface version of the Borel hierarchy, in which one uses uniformly computable countable unions and complements. The relativized notion leads to the hyperarithmetic degrees, a hyperarithmetic analogue of the Turing degrees.</p> <ul> <li>projective</li> </ul> <p>A real is <em>projective</em> if it can be defined by a description that quantifies only over the set of real numbers, plus natural number quantification and the primitive operations. The <a href="http://en.wikipedia.org/wiki/Projective_hierarchy" rel="nofollow">projective hierarchy</a> is stratified by considering the logical complexity of these definitions, with levels $\Sigma^1_n$ and $\Pi^1_n$. For example, the lightface analytic sets are $\Sigma^1_1$ and co-analytic is $\Pi^1_1$, with hyperarithmetic being $\Delta^1_1=\Sigma^1_1\cap\Pi^1_1$.</p> <ul> <li>constructible</li> </ul> <p>A real is <em>constructible</em> if it exists in G&ouml;del's <a href="http://en.wikipedia.org/wiki/Constructible_universe" rel="nofollow">constructible universe $L$</a>. The concept of relative constructibility gives rise to the constructibility degrees, by which $x\sim y\leftrightarrow L[x]=L[y]$, forming a rich hierarchy.</p> <ul> <li>ordinal-definable</li> </ul> <p>A real (or set) is <a href="http://en.wikipedia.org/wiki/Ordinal_definable" rel="nofollow"><em>ordinal-definable</em></a> if there is a definition of it in the language of set theory, using ordinal parameters. For example, the real whose $n^{th}$ binary digit is $1$ just in case $2^{\aleph_n}=\aleph_{n+1}$ is ordinal definable. The class HOD of all hereditarily ordinal definable sets satisfies ZFC, but can be strictly smaller than the universe of all sets.</p> <ul> <li>generic</li> </ul> <p>A real is <em>generic</em> over $L$ (or some other fixed universe $V$) if it exists in a forcing extension of $L$ (or $V$) by set forcing. Of course, it is relatively consistent with ZFC that every real is generic over $L$, since this is true in $L$ itself, but under some large cardinal axioms, there are reals, such as $0^\sharp$, that cannot be added by forcing over $L$.</p> <p>The higher levels of these latter hierarchies are further developed and stratified by the enormous variety of models of set theory arising from large cardinals, various inner model constructions, forcing extensions and so on, so that the hierarchy loses its linear nature, becoming instead a dense jungle of various interacting concepts of set theory.</p> http://mathoverflow.net/questions/53724/are-some-numbers-more-irrational-than-others/53756#53756 Answer by Mel Nathanson for Are some numbers more irrational than others? Mel Nathanson 2011-01-30T02:21:02Z 2011-01-30T02:21:02Z <p>It is easy to invent criteria to compare the irrationality of different numbers, but I doubt that anyone understands irrationality well enough to give a serious criterion. We do not even know the continued fraction for the cube root of 2. Nor is the "difficulty" or the length of an irrationality proof a reasonable criterion. A theorem only has a difficult or long proof until one finds an easy or short proof.</p> http://mathoverflow.net/questions/53724/are-some-numbers-more-irrational-than-others/54408#54408 Answer by Mel Nathanson for Are some numbers more irrational than others? Mel Nathanson 2011-02-05T15:14:37Z 2011-02-05T15:14:37Z <p>In response to a question about the comparative irrationality of real numbers, I wrote, "A theorem only has a difficult or long proof until one finds an easy or short proof." Mark Sapir replied, "There are only [a] finite number of proofs of length 10^10 so your last statement is wrong." I would argue, instead, that there are many contentious and, perhaps, wrong assumptions and philosophical misconceptions implicit in Sapir's sentence. For example, one could state and prove the theorem, "The sum of the first three odd numbers is nine." One could state and prove another theorem, "The sum of first five odd numbers is 25." One could state and prove another theorem, "The sum of first 100 odd numbers is 10,000." Continuing, one gets to statements of length greater than 10^10, and whose proofs would be even longer. Of course, someone might have the clever idea of proving inductively that, for all positive integers n, the sum of the first n odd numbers is n^2, and then one has a short proof of infinitely many theorems. It is exactly this kind of "exponential collapse," often called "progress in science," that I meant when I wrote a proof is long until one finds a short proof. I would be very interested to know if someone can really prove that there exist theorems that do not have short proofs. It is more likely that there are only finitely many theorems, and they all have short, simple, and elegant proofs. This, of course, is simply another description of Erdos' famous book. </p>