Mixing
How to construct a transcendental number
$begingroup$
I am doing a project about irrational and transcendental numbers and I was wondering how could I construct a "new" transcendental number. I know that all Liouville numbers are transcendental so this could be a good place to start however I wish to try and create one not necessarily belonging to that group of numbers. In addition to this I am aware of Liouville's theorem surrounding transcendental numbers and have also found a proof to how that the theorem is true and holds for Liouville's constant.
Once again I know about the Gelfond-Schneider theorem but the same idea applies. I would like to stay away from obvious substitutions i.e. $4^{sqrt{17}}$ is transcendental but not really "interesting". Also any strange theorems I would like to try and prove for the sake of completion. I don't want to just assert something and just have it there. I would like to be as thorough as possible.
Any help is greatly appreciated and thanks in advance
transcendental-numbers
$endgroup$
add a comment |
$begingroup$
I am doing a project about irrational and transcendental numbers and I was wondering how could I construct a "new" transcendental number. I know that all Liouville numbers are transcendental so this could be a good place to start however I wish to try and create one not necessarily belonging to that group of numbers. In addition to this I am aware of Liouville's theorem surrounding transcendental numbers and have also found a proof to how that the theorem is true and holds for Liouville's constant.
Once again I know about the Gelfond-Schneider theorem but the same idea applies. I would like to stay away from obvious substitutions i.e. $4^{sqrt{17}}$ is transcendental but not really "interesting". Also any strange theorems I would like to try and prove for the sake of completion. I don't want to just assert something and just have it there. I would like to be as thorough as possible.
Any help is greatly appreciated and thanks in advance
transcendental-numbers
$endgroup$
$begingroup$
Good question, but considering that you are researching the subject, maybe you could add some of your thoughts or ideas?
$endgroup$
– Yuriy S
Jan 28 at 13:00
1
$begingroup$
It would also help if you gave us some idea of what you know. Are you aware, say, of Liouville's Approximation Theorem?
$endgroup$
– lulu
Jan 28 at 13:01
add a comment |
$begingroup$
I am doing a project about irrational and transcendental numbers and I was wondering how could I construct a "new" transcendental number. I know that all Liouville numbers are transcendental so this could be a good place to start however I wish to try and create one not necessarily belonging to that group of numbers. In addition to this I am aware of Liouville's theorem surrounding transcendental numbers and have also found a proof to how that the theorem is true and holds for Liouville's constant.
Once again I know about the Gelfond-Schneider theorem but the same idea applies. I would like to stay away from obvious substitutions i.e. $4^{sqrt{17}}$ is transcendental but not really "interesting". Also any strange theorems I would like to try and prove for the sake of completion. I don't want to just assert something and just have it there. I would like to be as thorough as possible.
Any help is greatly appreciated and thanks in advance
transcendental-numbers
$endgroup$
I am doing a project about irrational and transcendental numbers and I was wondering how could I construct a "new" transcendental number. I know that all Liouville numbers are transcendental so this could be a good place to start however I wish to try and create one not necessarily belonging to that group of numbers. In addition to this I am aware of Liouville's theorem surrounding transcendental numbers and have also found a proof to how that the theorem is true and holds for Liouville's constant.
Once again I know about the Gelfond-Schneider theorem but the same idea applies. I would like to stay away from obvious substitutions i.e. $4^{sqrt{17}}$ is transcendental but not really "interesting". Also any strange theorems I would like to try and prove for the sake of completion. I don't want to just assert something and just have it there. I would like to be as thorough as possible.
Any help is greatly appreciated and thanks in advance
transcendental-numbers
transcendental-numbers
edited Jan 28 at 13:12
asked Jan 28 at 12:52
user610274
$begingroup$
Good question, but considering that you are researching the subject, maybe you could add some of your thoughts or ideas?
$endgroup$
– Yuriy S
Jan 28 at 13:00
1
$begingroup$
It would also help if you gave us some idea of what you know. Are you aware, say, of Liouville's Approximation Theorem?
$endgroup$
– lulu
Jan 28 at 13:01
add a comment |
$begingroup$
Good question, but considering that you are researching the subject, maybe you could add some of your thoughts or ideas?
$endgroup$
– Yuriy S
Jan 28 at 13:00
1
$begingroup$
It would also help if you gave us some idea of what you know. Are you aware, say, of Liouville's Approximation Theorem?
$endgroup$
– lulu
Jan 28 at 13:01
$begingroup$
Good question, but considering that you are researching the subject, maybe you could add some of your thoughts or ideas?
$endgroup$
– Yuriy S
Jan 28 at 13:00
$begingroup$
Good question, but considering that you are researching the subject, maybe you could add some of your thoughts or ideas?
$endgroup$
– Yuriy S
Jan 28 at 13:00
1
1
$begingroup$
It would also help if you gave us some idea of what you know. Are you aware, say, of Liouville's Approximation Theorem?
$endgroup$
– lulu
Jan 28 at 13:01
$begingroup$
It would also help if you gave us some idea of what you know. Are you aware, say, of Liouville's Approximation Theorem?
$endgroup$
– lulu
Jan 28 at 13:01
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Take your favorite polynomial, $p(x) := x^2-x-1$, and your favorite transcendental number $c := pi$. The number $p(c)$ is transcendental.
The key to transcendental numbers is polynomials with integer or rational coefficients. If $p(c)$ was algebraic, then there exists polynomials $q(x)$ such that $q(p(c))=0$ but then the composition $r(x):=q(p(x))$ is also a polynomial and $r(c)=0$ which would imply that $c$ is algebraic. The contrapositive statement is now proven.
answered Jan 28 at 13:01
SomosSomos
14.7k11337
$endgroup$
$begingroup$
Thanks!! Is there anyway to prove this? Also I feel like that I should also prove that π is transcendental and my lecturer has told me that that is outside the scope of my project.
$endgroup$
– user610274
Jan 28 at 13:07
3
$begingroup$
@AntRobinson the composition of polynomials is a polynomial, so if $p(c)$ was root of a polynomial, then so would be $c$
$endgroup$
– Pedro
Jan 28 at 13:26
$begingroup$
Brilliant thanks!
$endgroup$
– user610274
Jan 28 at 13:28
$begingroup$
Sorry to be pain but could you link where yo got this idea from? Is it from a book, just so that I have an extra reference for my report
$endgroup$
– user610274
Jan 28 at 14:20
1
$begingroup$
I think it's cheating to invoke known transcendentals such as $ pi $ or $e$ when "finding" a new one.
$endgroup$
– Carl Witthoft
Jan 28 at 20:23
|
show 2 more comments
$begingroup$
Every algebraic number is computable, so every uncomputable number is transcendental.
You have a wide variety of uncomputable numbers to choose from. If you object that you cannot 'construct' them, then you will have to be more precise in what you mean by 'construct'. After all, you cannot really 'construct' $π$ anyway; you can only compute finitely many digits of it.
Diagonalizing against algebraic numbers produces a computable transcendental number.
Basically, you can computably enumerate all triples $(Q,x,y)$ where $Q$ is an integer polynomial and $x,y$ are rationals such that $x<y$. Thus you can write an explicit program that represents a real $r$ in $[0,1)$ (i.e. on input $k$ outputs the $k$-th ternary digit), computing the $k$-th digit $d$ of $r$ as follows. Let $(Q,x,y)$ be the $k$-th triple in the enumeration. If $Q(x) < 0 < Q(y)$, then use binary search to find some $z ∈ [x,y]$ such that $Q(z) = 0$ to $k$ ternary digits, and let $d$ be the least digit (i.e. $0$ or $1$) that differs from the $k$-th digit of $z$. Otherwise, let $d = 0$.
You can prove that every algebraic number will be diagonalized against by $r$, since $r$ is a simple root of some nonzero polynomial (because every multiple root of a nonzero integer polynomial with multiplicity $m$ is a simple root of the $(m-1)$-th derivative of that polynomial), and every nonzero integer polynomial has finitely many roots so each root will be the unique root in some sufficiently small rational interval around it.
Someone pointed out to me an alternative diagonalization, which is to computably enumerate all nonzero integer polynomials and compute the desired real $r = 0.cdots$ by iteratively appending extra binary digits to avoid the roots of each polynomial in the enumeration. Consider each enumerated polynomial $Q$, and let $d$ be its degree. Then choose any $(d+1)$ distinct extensions of the current $r$ (at most $log_2(d+1)+1$ extra digits are needed), and let $s$ be one of them that is not a root of $Q$, which exists since $Q$ has at most $d$ roots. Compute some rational $δ > 0$ such that $Q(x) ≠ 0$ for every $x ∈ [s-δ,s+δ]$. (You can get this by unfolding the proof of continuity of $Q$ at $s ∈ [0,1]$, since $|Q(s)| > 0$.) Thus we can append extra digits to $r$ to ensure that the final $r$ is in the interval $[s-δ,s+δ]$. (At any point if $r$ has $k$ binary digits then the final $r$ would be in $[r,r+2^{-k}]$.)
answered Jan 29 at 10:06
user21820user21820
39.8k544158
$endgroup$
$begingroup$
In general, if we represent computable reals by digit-generating programs or rational approximation programs, there is a program $D$ that, given as input any program $A$ that enumerates a collection of computable reals, will produce as output some computable real not enumerated by $A$. The proof is exactly the same. So for example you can use $D$ to construct a computable real that is not expressible using arithmetic, polynomial-roots, exponentiation, logarithms, trigonometric functions, and whatever other (computable) special functions you wish.
$endgroup$
– user21820
Jan 29 at 12:33
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3090821%2fhow-to-construct-a-transcendental-number%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Take your favorite polynomial, $p(x) := x^2-x-1$, and your favorite transcendental number $c := pi$. The number $p(c)$ is transcendental.
The key to transcendental numbers is polynomials with integer or rational coefficients. If $p(c)$ was algebraic, then there exists polynomials $q(x)$ such that $q(p(c))=0$ but then the composition $r(x):=q(p(x))$ is also a polynomial and $r(c)=0$ which would imply that $c$ is algebraic. The contrapositive statement is now proven.
answered Jan 28 at 13:01
SomosSomos
14.7k11337
$endgroup$
$begingroup$
Thanks!! Is there anyway to prove this? Also I feel like that I should also prove that π is transcendental and my lecturer has told me that that is outside the scope of my project.
$endgroup$
– user610274
Jan 28 at 13:07
3
$begingroup$
@AntRobinson the composition of polynomials is a polynomial, so if $p(c)$ was root of a polynomial, then so would be $c$
$endgroup$
– Pedro
Jan 28 at 13:26
$begingroup$
Brilliant thanks!
$endgroup$
– user610274
Jan 28 at 13:28
$begingroup$
Sorry to be pain but could you link where yo got this idea from? Is it from a book, just so that I have an extra reference for my report
$endgroup$
– user610274
Jan 28 at 14:20
1
$begingroup$
I think it's cheating to invoke known transcendentals such as $ pi $ or $e$ when "finding" a new one.
$endgroup$
– Carl Witthoft
Jan 28 at 20:23
|
show 2 more comments
$begingroup$
Take your favorite polynomial, $p(x) := x^2-x-1$, and your favorite transcendental number $c := pi$. The number $p(c)$ is transcendental.
The key to transcendental numbers is polynomials with integer or rational coefficients. If $p(c)$ was algebraic, then there exists polynomials $q(x)$ such that $q(p(c))=0$ but then the composition $r(x):=q(p(x))$ is also a polynomial and $r(c)=0$ which would imply that $c$ is algebraic. The contrapositive statement is now proven.
answered Jan 28 at 13:01
SomosSomos
14.7k11337
$endgroup$
$begingroup$
Thanks!! Is there anyway to prove this? Also I feel like that I should also prove that π is transcendental and my lecturer has told me that that is outside the scope of my project.
$endgroup$
– user610274
Jan 28 at 13:07
3
$begingroup$
@AntRobinson the composition of polynomials is a polynomial, so if $p(c)$ was root of a polynomial, then so would be $c$
$endgroup$
– Pedro
Jan 28 at 13:26
$begingroup$
Brilliant thanks!
$endgroup$
– user610274
Jan 28 at 13:28
$begingroup$
Sorry to be pain but could you link where yo got this idea from? Is it from a book, just so that I have an extra reference for my report
$endgroup$
– user610274
Jan 28 at 14:20
1
$begingroup$
I think it's cheating to invoke known transcendentals such as $ pi $ or $e$ when "finding" a new one.
$endgroup$
– Carl Witthoft
Jan 28 at 20:23
|
show 2 more comments
$begingroup$
Take your favorite polynomial, $p(x) := x^2-x-1$, and your favorite transcendental number $c := pi$. The number $p(c)$ is transcendental.
The key to transcendental numbers is polynomials with integer or rational coefficients. If $p(c)$ was algebraic, then there exists polynomials $q(x)$ such that $q(p(c))=0$ but then the composition $r(x):=q(p(x))$ is also a polynomial and $r(c)=0$ which would imply that $c$ is algebraic. The contrapositive statement is now proven.
answered Jan 28 at 13:01
SomosSomos
14.7k11337
$endgroup$
Take your favorite polynomial, $p(x) := x^2-x-1$, and your favorite transcendental number $c := pi$. The number $p(c)$ is transcendental.
The key to transcendental numbers is polynomials with integer or rational coefficients. If $p(c)$ was algebraic, then there exists polynomials $q(x)$ such that $q(p(c))=0$ but then the composition $r(x):=q(p(x))$ is also a polynomial and $r(c)=0$ which would imply that $c$ is algebraic. The contrapositive statement is now proven.
answered Jan 28 at 13:01
SomosSomos
14.7k11337
edited Jan 28 at 16:32
answered Jan 28 at 13:01
SomosSomos
14.7k11337
answered Jan 28 at 13:01
SomosSomos
14.7k11337
answered Jan 28 at 13:01
SomosSomos
14.7k11337
14.7k11337
$begingroup$
Thanks!! Is there anyway to prove this? Also I feel like that I should also prove that π is transcendental and my lecturer has told me that that is outside the scope of my project.
$endgroup$
– user610274
Jan 28 at 13:07
3
$begingroup$
@AntRobinson the composition of polynomials is a polynomial, so if $p(c)$ was root of a polynomial, then so would be $c$
$endgroup$
– Pedro
Jan 28 at 13:26
$begingroup$
Brilliant thanks!
$endgroup$
– user610274
Jan 28 at 13:28
$begingroup$
Sorry to be pain but could you link where yo got this idea from? Is it from a book, just so that I have an extra reference for my report
$endgroup$
– user610274
Jan 28 at 14:20
1
$begingroup$
I think it's cheating to invoke known transcendentals such as $ pi $ or $e$ when "finding" a new one.
$endgroup$
– Carl Witthoft
Jan 28 at 20:23
|
show 2 more comments
$begingroup$
Thanks!! Is there anyway to prove this? Also I feel like that I should also prove that π is transcendental and my lecturer has told me that that is outside the scope of my project.
$endgroup$
– user610274
Jan 28 at 13:07
3
$begingroup$
@AntRobinson the composition of polynomials is a polynomial, so if $p(c)$ was root of a polynomial, then so would be $c$
$endgroup$
– Pedro
Jan 28 at 13:26
$begingroup$
Brilliant thanks!
$endgroup$
– user610274
Jan 28 at 13:28
$begingroup$
Sorry to be pain but could you link where yo got this idea from? Is it from a book, just so that I have an extra reference for my report
$endgroup$
– user610274
Jan 28 at 14:20
1
$begingroup$
I think it's cheating to invoke known transcendentals such as $ pi $ or $e$ when "finding" a new one.
$endgroup$
– Carl Witthoft
Jan 28 at 20:23
$begingroup$
Thanks!! Is there anyway to prove this? Also I feel like that I should also prove that π is transcendental and my lecturer has told me that that is outside the scope of my project.
$endgroup$
– user610274
Jan 28 at 13:07
$begingroup$
Thanks!! Is there anyway to prove this? Also I feel like that I should also prove that π is transcendental and my lecturer has told me that that is outside the scope of my project.
$endgroup$
– user610274
Jan 28 at 13:07
3
3
$begingroup$
@AntRobinson the composition of polynomials is a polynomial, so if $p(c)$ was root of a polynomial, then so would be $c$
$endgroup$
– Pedro
Jan 28 at 13:26
$begingroup$
@AntRobinson the composition of polynomials is a polynomial, so if $p(c)$ was root of a polynomial, then so would be $c$
$endgroup$
– Pedro
Jan 28 at 13:26
$begingroup$
Brilliant thanks!
$endgroup$
– user610274
Jan 28 at 13:28
$begingroup$
Brilliant thanks!
$endgroup$
– user610274
Jan 28 at 13:28
$begingroup$
Sorry to be pain but could you link where yo got this idea from? Is it from a book, just so that I have an extra reference for my report
$endgroup$
– user610274
Jan 28 at 14:20
$begingroup$
Sorry to be pain but could you link where yo got this idea from? Is it from a book, just so that I have an extra reference for my report
$endgroup$
– user610274
Jan 28 at 14:20
1
1
$begingroup$
I think it's cheating to invoke known transcendentals such as $ pi $ or $e$ when "finding" a new one.
$endgroup$
– Carl Witthoft
Jan 28 at 20:23
$begingroup$
I think it's cheating to invoke known transcendentals such as $ pi $ or $e$ when "finding" a new one.
$endgroup$
– Carl Witthoft
Jan 28 at 20:23
|
show 2 more comments
$begingroup$
Every algebraic number is computable, so every uncomputable number is transcendental.
You have a wide variety of uncomputable numbers to choose from. If you object that you cannot 'construct' them, then you will have to be more precise in what you mean by 'construct'. After all, you cannot really 'construct' $π$ anyway; you can only compute finitely many digits of it.
Diagonalizing against algebraic numbers produces a computable transcendental number.
Basically, you can computably enumerate all triples $(Q,x,y)$ where $Q$ is an integer polynomial and $x,y$ are rationals such that $x<y$. Thus you can write an explicit program that represents a real $r$ in $[0,1)$ (i.e. on input $k$ outputs the $k$-th ternary digit), computing the $k$-th digit $d$ of $r$ as follows. Let $(Q,x,y)$ be the $k$-th triple in the enumeration. If $Q(x) < 0 < Q(y)$, then use binary search to find some $z ∈ [x,y]$ such that $Q(z) = 0$ to $k$ ternary digits, and let $d$ be the least digit (i.e. $0$ or $1$) that differs from the $k$-th digit of $z$. Otherwise, let $d = 0$.
You can prove that every algebraic number will be diagonalized against by $r$, since $r$ is a simple root of some nonzero polynomial (because every multiple root of a nonzero integer polynomial with multiplicity $m$ is a simple root of the $(m-1)$-th derivative of that polynomial), and every nonzero integer polynomial has finitely many roots so each root will be the unique root in some sufficiently small rational interval around it.
Someone pointed out to me an alternative diagonalization, which is to computably enumerate all nonzero integer polynomials and compute the desired real $r = 0.cdots$ by iteratively appending extra binary digits to avoid the roots of each polynomial in the enumeration. Consider each enumerated polynomial $Q$, and let $d$ be its degree. Then choose any $(d+1)$ distinct extensions of the current $r$ (at most $log_2(d+1)+1$ extra digits are needed), and let $s$ be one of them that is not a root of $Q$, which exists since $Q$ has at most $d$ roots. Compute some rational $δ > 0$ such that $Q(x) ≠ 0$ for every $x ∈ [s-δ,s+δ]$. (You can get this by unfolding the proof of continuity of $Q$ at $s ∈ [0,1]$, since $|Q(s)| > 0$.) Thus we can append extra digits to $r$ to ensure that the final $r$ is in the interval $[s-δ,s+δ]$. (At any point if $r$ has $k$ binary digits then the final $r$ would be in $[r,r+2^{-k}]$.)
answered Jan 29 at 10:06
user21820user21820
39.8k544158
$endgroup$
$begingroup$
In general, if we represent computable reals by digit-generating programs or rational approximation programs, there is a program $D$ that, given as input any program $A$ that enumerates a collection of computable reals, will produce as output some computable real not enumerated by $A$. The proof is exactly the same. So for example you can use $D$ to construct a computable real that is not expressible using arithmetic, polynomial-roots, exponentiation, logarithms, trigonometric functions, and whatever other (computable) special functions you wish.
$endgroup$
– user21820
Jan 29 at 12:33
add a comment |
$begingroup$
Every algebraic number is computable, so every uncomputable number is transcendental.
You have a wide variety of uncomputable numbers to choose from. If you object that you cannot 'construct' them, then you will have to be more precise in what you mean by 'construct'. After all, you cannot really 'construct' $π$ anyway; you can only compute finitely many digits of it.
Diagonalizing against algebraic numbers produces a computable transcendental number.
Basically, you can computably enumerate all triples $(Q,x,y)$ where $Q$ is an integer polynomial and $x,y$ are rationals such that $x<y$. Thus you can write an explicit program that represents a real $r$ in $[0,1)$ (i.e. on input $k$ outputs the $k$-th ternary digit), computing the $k$-th digit $d$ of $r$ as follows. Let $(Q,x,y)$ be the $k$-th triple in the enumeration. If $Q(x) < 0 < Q(y)$, then use binary search to find some $z ∈ [x,y]$ such that $Q(z) = 0$ to $k$ ternary digits, and let $d$ be the least digit (i.e. $0$ or $1$) that differs from the $k$-th digit of $z$. Otherwise, let $d = 0$.
You can prove that every algebraic number will be diagonalized against by $r$, since $r$ is a simple root of some nonzero polynomial (because every multiple root of a nonzero integer polynomial with multiplicity $m$ is a simple root of the $(m-1)$-th derivative of that polynomial), and every nonzero integer polynomial has finitely many roots so each root will be the unique root in some sufficiently small rational interval around it.
Someone pointed out to me an alternative diagonalization, which is to computably enumerate all nonzero integer polynomials and compute the desired real $r = 0.cdots$ by iteratively appending extra binary digits to avoid the roots of each polynomial in the enumeration. Consider each enumerated polynomial $Q$, and let $d$ be its degree. Then choose any $(d+1)$ distinct extensions of the current $r$ (at most $log_2(d+1)+1$ extra digits are needed), and let $s$ be one of them that is not a root of $Q$, which exists since $Q$ has at most $d$ roots. Compute some rational $δ > 0$ such that $Q(x) ≠ 0$ for every $x ∈ [s-δ,s+δ]$. (You can get this by unfolding the proof of continuity of $Q$ at $s ∈ [0,1]$, since $|Q(s)| > 0$.) Thus we can append extra digits to $r$ to ensure that the final $r$ is in the interval $[s-δ,s+δ]$. (At any point if $r$ has $k$ binary digits then the final $r$ would be in $[r,r+2^{-k}]$.)
answered Jan 29 at 10:06
user21820user21820
39.8k544158
$endgroup$
$begingroup$
In general, if we represent computable reals by digit-generating programs or rational approximation programs, there is a program $D$ that, given as input any program $A$ that enumerates a collection of computable reals, will produce as output some computable real not enumerated by $A$. The proof is exactly the same. So for example you can use $D$ to construct a computable real that is not expressible using arithmetic, polynomial-roots, exponentiation, logarithms, trigonometric functions, and whatever other (computable) special functions you wish.
$endgroup$
– user21820
Jan 29 at 12:33
add a comment |
$begingroup$
Every algebraic number is computable, so every uncomputable number is transcendental.
You have a wide variety of uncomputable numbers to choose from. If you object that you cannot 'construct' them, then you will have to be more precise in what you mean by 'construct'. After all, you cannot really 'construct' $π$ anyway; you can only compute finitely many digits of it.
Diagonalizing against algebraic numbers produces a computable transcendental number.
Basically, you can computably enumerate all triples $(Q,x,y)$ where $Q$ is an integer polynomial and $x,y$ are rationals such that $x<y$. Thus you can write an explicit program that represents a real $r$ in $[0,1)$ (i.e. on input $k$ outputs the $k$-th ternary digit), computing the $k$-th digit $d$ of $r$ as follows. Let $(Q,x,y)$ be the $k$-th triple in the enumeration. If $Q(x) < 0 < Q(y)$, then use binary search to find some $z ∈ [x,y]$ such that $Q(z) = 0$ to $k$ ternary digits, and let $d$ be the least digit (i.e. $0$ or $1$) that differs from the $k$-th digit of $z$. Otherwise, let $d = 0$.
You can prove that every algebraic number will be diagonalized against by $r$, since $r$ is a simple root of some nonzero polynomial (because every multiple root of a nonzero integer polynomial with multiplicity $m$ is a simple root of the $(m-1)$-th derivative of that polynomial), and every nonzero integer polynomial has finitely many roots so each root will be the unique root in some sufficiently small rational interval around it.
Someone pointed out to me an alternative diagonalization, which is to computably enumerate all nonzero integer polynomials and compute the desired real $r = 0.cdots$ by iteratively appending extra binary digits to avoid the roots of each polynomial in the enumeration. Consider each enumerated polynomial $Q$, and let $d$ be its degree. Then choose any $(d+1)$ distinct extensions of the current $r$ (at most $log_2(d+1)+1$ extra digits are needed), and let $s$ be one of them that is not a root of $Q$, which exists since $Q$ has at most $d$ roots. Compute some rational $δ > 0$ such that $Q(x) ≠ 0$ for every $x ∈ [s-δ,s+δ]$. (You can get this by unfolding the proof of continuity of $Q$ at $s ∈ [0,1]$, since $|Q(s)| > 0$.) Thus we can append extra digits to $r$ to ensure that the final $r$ is in the interval $[s-δ,s+δ]$. (At any point if $r$ has $k$ binary digits then the final $r$ would be in $[r,r+2^{-k}]$.)
answered Jan 29 at 10:06
user21820user21820
39.8k544158
$endgroup$
Every algebraic number is computable, so every uncomputable number is transcendental.
You have a wide variety of uncomputable numbers to choose from. If you object that you cannot 'construct' them, then you will have to be more precise in what you mean by 'construct'. After all, you cannot really 'construct' $π$ anyway; you can only compute finitely many digits of it.
Diagonalizing against algebraic numbers produces a computable transcendental number.
Basically, you can computably enumerate all triples $(Q,x,y)$ where $Q$ is an integer polynomial and $x,y$ are rationals such that $x<y$. Thus you can write an explicit program that represents a real $r$ in $[0,1)$ (i.e. on input $k$ outputs the $k$-th ternary digit), computing the $k$-th digit $d$ of $r$ as follows. Let $(Q,x,y)$ be the $k$-th triple in the enumeration. If $Q(x) < 0 < Q(y)$, then use binary search to find some $z ∈ [x,y]$ such that $Q(z) = 0$ to $k$ ternary digits, and let $d$ be the least digit (i.e. $0$ or $1$) that differs from the $k$-th digit of $z$. Otherwise, let $d = 0$.
You can prove that every algebraic number will be diagonalized against by $r$, since $r$ is a simple root of some nonzero polynomial (because every multiple root of a nonzero integer polynomial with multiplicity $m$ is a simple root of the $(m-1)$-th derivative of that polynomial), and every nonzero integer polynomial has finitely many roots so each root will be the unique root in some sufficiently small rational interval around it.
Someone pointed out to me an alternative diagonalization, which is to computably enumerate all nonzero integer polynomials and compute the desired real $r = 0.cdots$ by iteratively appending extra binary digits to avoid the roots of each polynomial in the enumeration. Consider each enumerated polynomial $Q$, and let $d$ be its degree. Then choose any $(d+1)$ distinct extensions of the current $r$ (at most $log_2(d+1)+1$ extra digits are needed), and let $s$ be one of them that is not a root of $Q$, which exists since $Q$ has at most $d$ roots. Compute some rational $δ > 0$ such that $Q(x) ≠ 0$ for every $x ∈ [s-δ,s+δ]$. (You can get this by unfolding the proof of continuity of $Q$ at $s ∈ [0,1]$, since $|Q(s)| > 0$.) Thus we can append extra digits to $r$ to ensure that the final $r$ is in the interval $[s-δ,s+δ]$. (At any point if $r$ has $k$ binary digits then the final $r$ would be in $[r,r+2^{-k}]$.)
answered Jan 29 at 10:06
user21820user21820
39.8k544158
edited Feb 3 at 12:14
answered Jan 29 at 10:06
user21820user21820
39.8k544158
answered Jan 29 at 10:06
user21820user21820
39.8k544158
answered Jan 29 at 10:06
user21820user21820
39.8k544158
39.8k544158
$begingroup$
In general, if we represent computable reals by digit-generating programs or rational approximation programs, there is a program $D$ that, given as input any program $A$ that enumerates a collection of computable reals, will produce as output some computable real not enumerated by $A$. The proof is exactly the same. So for example you can use $D$ to construct a computable real that is not expressible using arithmetic, polynomial-roots, exponentiation, logarithms, trigonometric functions, and whatever other (computable) special functions you wish.
$endgroup$
– user21820
Jan 29 at 12:33
add a comment |
$begingroup$
In general, if we represent computable reals by digit-generating programs or rational approximation programs, there is a program $D$ that, given as input any program $A$ that enumerates a collection of computable reals, will produce as output some computable real not enumerated by $A$. The proof is exactly the same. So for example you can use $D$ to construct a computable real that is not expressible using arithmetic, polynomial-roots, exponentiation, logarithms, trigonometric functions, and whatever other (computable) special functions you wish.
$endgroup$
– user21820
Jan 29 at 12:33
$begingroup$
In general, if we represent computable reals by digit-generating programs or rational approximation programs, there is a program $D$ that, given as input any program $A$ that enumerates a collection of computable reals, will produce as output some computable real not enumerated by $A$. The proof is exactly the same. So for example you can use $D$ to construct a computable real that is not expressible using arithmetic, polynomial-roots, exponentiation, logarithms, trigonometric functions, and whatever other (computable) special functions you wish.
$endgroup$
– user21820
Jan 29 at 12:33
$begingroup$
In general, if we represent computable reals by digit-generating programs or rational approximation programs, there is a program $D$ that, given as input any program $A$ that enumerates a collection of computable reals, will produce as output some computable real not enumerated by $A$. The proof is exactly the same. So for example you can use $D$ to construct a computable real that is not expressible using arithmetic, polynomial-roots, exponentiation, logarithms, trigonometric functions, and whatever other (computable) special functions you wish.
$endgroup$
– user21820
Jan 29 at 12:33
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3090821%2fhow-to-construct-a-transcendental-number%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Good question, but considering that you are researching the subject, maybe you could add some of your thoughts or ideas?
$endgroup$
– Yuriy S
Jan 28 at 13:00
1
$begingroup$
It would also help if you gave us some idea of what you know. Are you aware, say, of Liouville's Approximation Theorem?
$endgroup$
– lulu
Jan 28 at 13:01