Algebraic and Transcendental
A number is called algebraic if it is the root of a nonzero polynomial with integral coefficients (or, equivalently, rational coefficients); otherwise it is transcendental.
Item: there exists a nonintegral c > 1 such that c^n 'converges to the integers': that is, for any eps > 0 there's an N > 0 such that c^n is within eps of some integer, for all n > N. (I think the golden mean was an example, but I can't find or remember the reference book at the moment.)
Item: it is apparently open whether any such number can be transcendental.
***
Next up, two questions of my own on algebraic numbers. Possibly easy, possibly silly, but I don't know the answers.
Define the interleave of two numbers
b = 0.b_1b_2b_3... and c = 0.c_1c_2c_3...
(both in [0, 1], and using the 'correct' binary expansions) as
b@c = 0.b_1c_1b_2c_2...
1) Suppose b, c are algebraic. Must b@c be algebraic?
2) The other direction. Suppose b@c is algebraic. Must b, c be algebraic?
In both cases, I am inclined towards doubt.
***
Final thoughts (and these are observations others have made as well)... computational complexity theory seems to have certain things in common with transcendental number theory:
-an interest in impossibility/inexpressibility results;
-markedly slow progress on seemingly basic
questions--is (pi + e) irrational? does P = NP?
-attempts to use statistical and otherwise 'constructive' properties as sieves to distinguish simple objects from complicated ones.
So, could complexity theorists benefit from interacting and learning from transcendental number theorists? If nothing else, looking back on their long historical march might teach us patience and an appreciation for incremental progress.
Item: there exists a nonintegral c > 1 such that c^n 'converges to the integers': that is, for any eps > 0 there's an N > 0 such that c^n is within eps of some integer, for all n > N. (I think the golden mean was an example, but I can't find or remember the reference book at the moment.)
Item: it is apparently open whether any such number can be transcendental.
***
Next up, two questions of my own on algebraic numbers. Possibly easy, possibly silly, but I don't know the answers.
Define the interleave of two numbers
b = 0.b_1b_2b_3... and c = 0.c_1c_2c_3...
(both in [0, 1], and using the 'correct' binary expansions) as
b@c = 0.b_1c_1b_2c_2...
1) Suppose b, c are algebraic. Must b@c be algebraic?
2) The other direction. Suppose b@c is algebraic. Must b, c be algebraic?
In both cases, I am inclined towards doubt.
***
Final thoughts (and these are observations others have made as well)... computational complexity theory seems to have certain things in common with transcendental number theory:
-an interest in impossibility/inexpressibility results;
-markedly slow progress on seemingly basic
questions--is (pi + e) irrational? does P = NP?
-attempts to use statistical and otherwise 'constructive' properties as sieves to distinguish simple objects from complicated ones.
So, could complexity theorists benefit from interacting and learning from transcendental number theorists? If nothing else, looking back on their long historical march might teach us patience and an appreciation for incremental progress.
Labels: general math, puzzles
posted by Andy D at
3:45 PM
19 Comments:
"So, could complexity theorists benefit from interacting and learning from transcendental number theorists?"
Not really. If they are both slow, there's no real chance that taken together they'll be fast. (For a constructive proof, consider two slow horses pulling each other.)
"If nothing else, looking back on their long historical march might teach us patience and an appreciation for incremental progress."
Yes, patience it will teach us for sure.
By
Anonymous, at 6:58 PM
Andy,
I think that the answer to your questions may possibly be found in the field of combinatorics on words. This is a classic field at the boundary of TCS and combinatorics.
It so happens that last Friday I attended a talk by Amy Glen, a colleague of mine who is about to deliver an invited address at "The Interface Between Number Theory and Dynamical Systems", AMS Meeting, University of Illinois at Urbana-Champaign, USA. The talk, entitled Palindromic properties of infinite sequences with applications to Number Theory, discussed progress on questions like the ones you raise in your post. You can find the slides here, in case you are interested.
By
Luca Aceto, at 5:25 AM
Thanks for the pointers, Luca! I've been meaning to get a better handle on what exactly 'combinatorics on words' is all about.
By
Andy D, at 11:46 AM
My pleasure. I guess that the standard references for the area are the books by Lothaire (a pen name for a whole bunch of authors), which you can find here. See also this Google book.
By
Luca Aceto, at 2:40 PM
Hi Andy,
Is there a motivation for this question of yours? Does it tie in to Complexity somehow, or is it more of a musing?
By
David Chen, at 3:19 PM
Definitely musing. But it's at least notionally related to complexity questions: if we combine two 'simple' things, is the result simple?
Actually David, your question reminded me of another investigation I made into algebraic numbers with a notional complexity connection--so thanks, and stay tuned for the next post...
By
Andy D, at 3:51 PM
I think the answer to the first one is NO. This is 'supported' by a conjecture believed to be true.
Let A be an irrational algebraic number. Let B = 0.1111.... = 1/9. B is also algebraic.
A@B = 0.a_11a_21....
It is easy to see that A@B cannot be rational [since it is non-periodic under assumption that A is rational]. Hence by the conjecture in this paper :
http://www-irma.u-strasbg.fr/~bugeaud/travaux/siauliaidef.pdf
If we assume A@B is algebraic, then it also irrational.
Thus p(n,A@B,10) = 10^n. However, a block of length n, that does not contain 1's is impossible to find. so p(n,A@B,10) <= 10^ceil(n/2).
By
Anonymous, at 11:53 PM
I think the thing about the golden mean can be seen as follows: let a be the golden mean (1 + sqrt(5))/2, and b its conjugate (1 - sqrt(5))/2.
Then the claim is that a^n + b^n is an integer for every natural number n, which would settle it, since |b| < 1 so b^n decreases steadily. We have a + b = 1, and a - b = -1. Assume that for all m < n, a^m + b^m is an integer. On one hand, for every n, (a + b)^n = 1, in particular this is an integer. On the other hand, its binomial expansion is a^n + b^n + Sum(c_k a^k b^(n - k) + b^k a^(n - k)), (if n is odd) where c_k is an integer (a binomial coefficient), and the sum is over all k < n/2 (when n is even, there is an extra term which is easily seen to be an integer). Now a^k b^(n - k) + b^k a^(n - k)) = (ab)^k (b^(n - 2k) + a^(n - 2k)) is an integer for each k by assumption, so a^n + b^n also must be.
By
Unknown, at 11:15 AM
Actually the same argument holds for any real quadratic integer a whose conjugate b is smaller than 1 in absolute value. Never realised that. (a quadratic integer is a root of a monic quadratic polynomial with integer coefficients, its conjugate is the other root)
By
Unknown, at 2:17 PM
Doetoe and anon--thanks for your interest and helpful comments!
By
Andy D, at 2:27 PM
This comment has been removed by the author.
By
Unknown, at 5:54 PM
You're welcome! One little correction: above I wrote a - b = -1 where I meant ab = -1 (which is used later on, or at least it is used that ab is an integer)
By
Unknown, at 5:58 PM
This comment has been removed by a blog administrator.
By
generic viagra, at 11:28 AM
This comment has been removed by a blog administrator.
By
buy viagra, at 6:36 PM
testing MathJax:
$\sqrt{n} + \log(n) = 2^{2^n}$.
By
Anonymous, at 2:14 PM
An equation like
\[ 2^{2^{2^n}} = \exp(4) + a_{n} + a_{b_n} \]
should be easy to display
By
Anonymous, at 2:16 PM
How about $\varepsilon$
By
Anonymous, at 2:21 PM
This was very helpful, thank you!
By
Viagra, at 11:44 AM
Hey! Coach Factory Online simply wanted to say your website is one of the nicely laid out, most inspirational I have come across in quite a while.
By
Coach Factory Online, at 2:27 AM
Post a Comment
<< Home