Return to Answer

Every answer before points You into algebraic complexity theory which is very fashionable today. I would like to try to point in some other direction, which probably is not what You are looking for, but is in my opinion interesting. I have hope that other than usual look is interesting and is not just misinterpretation of Your question.

Say I'm given some finite precision complex number, which I'm told is algebraic over \mathbb{Q}. Is there some well defined notion of arithmetic complexity which can allow me to deduce exactly what algebraic number this finite precision number represents?

Finite precision number is rational number. Then it has finite representation as continued fraction or as decimal number with finite number of digits. Say last digit is $a_n$ which means that we know Your number as $A=...a_0 + a_1/10 + a_2/10^2+... + a_n/10^n$ Then as You may see from decimal representation such number represents whole interval $I=[A,A+(a_n+1)/10^n]$. So as You ask for algebraic numbers, it may represent every algebraic number within this interval.

The other way to look at is is to use Stern-Brocot tree which is by means of continued fraction $A=[b_0;b_1,b_2,...,b_k]$ for some k. Then number A represents the whole tree when A is a root of it, and every branch of this tree, finite or infinite represents some number. It is interesting, that there You may say that every possible subtree with root in A may be represented by sequences of turns like $LLRRLLLLRLRLLR...$ (XX) on the tree, where R means right, and L means left, finite or infinite. There are interesting relation to Minkowski question mark function and Cantor function.

Then if I understand right, it is possible to reformulate Your question and say that You are asking for algebraic numbers represented within given interval or represented by certain sequences within giver family of sequences like (XX).

As You may see subtree of Stern-Brockot tree is isomorphic to the whole tree, and it is obvious that within given interval You may find infinite number of algebraic numbers. So in fact if You will see any pattern for algebraic number in given interval ( given with some procession) then You may reformulate it as property of whole set of algebraic numbers. And up to Your question: within given interval there is infinite subset of algebraic numbers with any computational complexity. That is because within subtree of Stern-Brockot tree there are presented sequences of any Kolmogorov measure You may think of. Stating finite precision, in fact You give some very beginning sequence in a tree, but not the infinite possible rest.

Interesting case is to ask if there exists any patterns for S-B tree or for any other (decimal, hexadecimal etc) representation for a numbers which may give us insight into property of numbers ( there are some, such simple as divisibility by 2 for example or much more complicated). For example is there any property in any representation ( possibly effective, not straight from the definition of algebraic number) which allows us to say that given number is algebraic, or algebraic of specified kind? As far as I know there is no pattern in continued fractions coefficients for general algebraic number, although, You may find pattern in numbers which are roots of quadratic diofantine equations. So Your question in general has no answer,but there are some patterns in known representations of numbers which gives us some classes of algebraic numbers: for example quadratic one. Maybe someday someone will find other patterns/representations which provide us other possibilities...

Every answer before points You into algebraic complexity theory which is very fashionable today. I would like to try to point in some other direction, which probably is not what You are looking for, but is in my opinion interesting. I have hope that other than usual look is interesting and is not just misinterpretation of Your question.

Say I'm given some finite precision complex number, which I'm told is algebraic over $\mathbb{Q}$. Is there some well defined notion of arithmetic complexity which can allow me to deduce exactly what algebraic number this finite precision number represents?

Finite precision number is rational number. Then it has finite representation as continued fraction or as decimal number with finite number of digits. Say last digit is $a_n$ which means that we know Your number as $A=...a_0 + a_1/10 + a_2/10^2+... + a_n/10^n$ Then as You may see from decimal representation such number represents whole interval $I=[A,A+(a_n+1)/10^n]$. So as You ask for algebraic numbers, it may represent every algebraic number within this interval.

The other way to look at is is to use Stern-Brocot tree which is by means of continued fraction $A=[b_0;b_1,b_2,...,b_k]$ for some k. Then number A represents the whole tree when A is a root of it, and every branch of this tree, finite or infinite represents some number. It is interesting, that there You may say that every possible subtree with root in A may be represented by sequences of turns like $LLRRLLLLRLRLLR...$ (XX) on the tree, where R means right, and L means left, finite or infinite. There are interesting relation to Minkowski question mark function and Cantor function.

Then if I understand right, it is possible to reformulate Your question and say that You are asking for algebraic numbers represented within given interval or represented by certain sequences within giver family of sequences like (XX).

As You may see subtree of Stern-Brocot tree is isomorphic to the whole tree, and it is obvious that within given interval You may find infinite number of algebraic numbers. So in fact if You will see any pattern for algebraic number in given interval ( given with some procession) then You may reformulate it as property of whole set of algebraic numbers. And up to Your question: within given interval there is infinite subset of algebraic numbers with any computational complexity. That is because within subtree of Stern-Brocot tree there are presented sequences of any Kolmogorov measure You may think of. Stating finite precision, in fact You give some very beginning sequence in a tree, but not the infinite possible rest.

Interesting case is to ask if there exists any patterns for S-B tree or for any other (decimal, hexadecimal etc) representation for a numbers which may give us insight into property of numbers ( there are some, such simple as divisibility by 2 for example or much more complicated). For example is there any property in any representation ( possibly effective, not straight from the definition of algebraic number) which allows us to say that given number is algebraic, or algebraic of specified kind? As far as I know there is no pattern in continued fractions coefficients for general algebraic number, although, You may find pattern in numbers which are roots of quadratic diofantine equations. So Your question in general has no answer,but there are some patterns in known representations of numbers which gives us some classes of algebraic numbers: for example quadratic one. Maybe someday someone will find other patterns/representations which provide us other possibilities...

Every answer before points You into algebraic complexity theory which is very fashionable today. I would like to try to point in some other direction, which probably is not what You are looking for, but is in my opinion interesting. I have hope that other than usual look is interesting and is not just misinterpretation of Your question.

Say I'm given some finite precision complex number, which I'm told is algebraic over \mathbb{Q}. Is there some well defined notion of arithmetic complexity which can allow me to deduce exactly what algebraic number this finite precision number represents?

Finite precision number is rational number. Then it has finite representation as continued fraction or as decimal number with finite number of digits. Say last digit is $a_n$ which means that we know Your number as $A=...a_0 + a_1/10 + a_2/10^2+... + a_n/10^n$ Then as You may see from decimal representation such number represents whole interval $I=[A,A+(a_n+1)/10^n]$. So as You ask for algebraic numbers, it may represent every algebraic number within this interval.

The other way to look at is is to use Stern-Brocot tree which is by means of continued fraction $A=[b_0;b_1,b_2,...,b_k]$ for some k. Then number A represents the whole tree when A is a root of it, and every branch of this tree, finite or infinite represents some number. It is interesting, that there You may say that every possible subtree with root in A may be represented by sequences of turns like $LLRRLLLLRLRLLR...$ (XX) on the tree, where R means right, and L means left, finite or infinite. There are interesting relation to Minkowski question mark function and Cantor function.

Then if I understand right, it is possible to reformulate Your question and say that You are asking for algebraic numbers represented within given interval or represented by certain sequences within giver family of sequences like (XX).

As You may see subtree of Stern-Brockot tree is isomorphic to the whole tree, and it is obvious that within given interval You may find infinite number of algebraic numbers. So in fact if You will see any pattern for algebraic number in given interval ( given with some procession) then You may reformulate it as property of whole set of algebraic numbers. And up to Your question: within given interval there is infinite subset of algebraic numbers with any computational complexity. That is because within subtree of Stern-Brockot tree there are presented sequences of any Kolmogorov measure You may think of. Stating finite precision, in fact You give some very beginning sequence in a tree, but not the infinite possible rest.

Interesting case is to ask if there exists any patterns for S-B tree or for any other (decimal, hexadecimal etc) representation for a numbers which may give us insight into property of numbers ( there are some, such simple as divisibility by 2 for example or much more complicated). For example is there any property in any representation ( possibly effective, not straight from the definition of algebraic number) which allows us to say that given number is algebraic, or algebraic of specified kind. Is far as I know there is no pattern in continued fractions coefficients for algebraic number, although, You may find pattern in numbers which are roots of quadratic diofantine equations. So Your question in general has no answer,but there are some patterns in known representations of numbers which gives us some classes of algebraic numbers: for example quadratic one. Maybe someday someone will find other patterns/representations which provide us other possibilities...

Every answer before points You into algebraic complexity theory which is very fashionable today. I would like to try to point in some other direction, which probably is not what You are looking for, but is in my opinion interesting. I have hope that other than usual look is interesting and is not just misinterpretation of Your question.

Say I'm given some finite precision complex number, which I'm told is algebraic over \mathbb{Q}. Is there some well defined notion of arithmetic complexity which can allow me to deduce exactly what algebraic number this finite precision number represents?

Finite precision number is rational number. Then it has finite representation as continued fraction or as decimal number with finite number of digits. Say last digit is $a_n$ which means that we know Your number as $A=...a_0 + a_1/10 + a_2/10^2+... + a_n/10^n$ Then as You may see from decimal representation such number represents whole interval $I=[A,A+(a_n+1)/10^n]$. So as You ask for algebraic numbers, it may represent every algebraic number within this interval.

The other way to look at is is to use Stern-Brocot tree which is by means of continued fraction $A=[b_0;b_1,b_2,...,b_k]$ for some k. Then number A represents the whole tree when A is a root of it, and every branch of this tree, finite or infinite represents some number. It is interesting, that there You may say that every possible subtree with root in A may be represented by sequences of turns like $LLRRLLLLRLRLLR...$ (XX) on the tree, where R means right, and L means left, finite or infinite. There are interesting relation to Minkowski question mark function and Cantor function.

Then if I understand right, it is possible to reformulate Your question and say that You are asking for algebraic numbers represented within given interval or represented by certain sequences within giver family of sequences like (XX).

As You may see subtree of Stern-Brockot tree is isomorphic to the whole tree, and it is obvious that within given interval You may find infinite number of algebraic numbers. So in fact if You will see any pattern for algebraic number in given interval ( given with some procession) then You may reformulate it as property of whole set of algebraic numbers. And up to Your question: within given interval there is infinite subset of algebraic numbers with any computational complexity. That is because within subtree of Stern-Brockot tree there are presented sequences of any Kolmogorov measure You may think of. Stating finite precision, in fact You give some very beginning sequence in a tree, but not the infinite possible rest.

Interesting case is to ask if there exists any patterns for S-B tree or for any other (decimal, hexadecimal etc) representation for a numbers which may give us insight into property of numbers ( there are some, such simple as divisibility by 2 for example or much more complicated). For example is there any property in any representation ( possibly effective, not straight from the definition of algebraic number) which allows us to say that given number is algebraic, or algebraic of specified kind? As far as I know there is no pattern in continued fractions coefficients for general algebraic number, although, You may find pattern in numbers which are roots of quadratic diofantine equations. So Your question in general has no answer,but there are some patterns in known representations of numbers which gives us some classes of algebraic numbers: for example quadratic one. Maybe someday someone will find other patterns/representations which provide us other possibilities...

Every answer before points You into algebraic complexity theory which is very fashionable today. I would like to try to point in some other direction, which probably is not what You are looking for, but is in my opinion interesting. I have hope that other than usual look is interesting and is not just misinterpretation of Your question.

Say I'm given some finite precision complex number, which I'm told is algebraic over \mathbb{Q}. Is there some well defined notion of arithmetic complexity which can allow me to deduce exactly what algebraic number this finite precision number represents?

Finite precision number is rational number. Then it has finite representation as continues fraction or as decimal number with finite number of digits. Say last digit is $a_n$ which means that we know Your number as $A=...a_0 + a_1/10 + a_2/10^2+... + a_n/10^n$ Then as You may see from decimal representation such number represents whole interval $I=[A,A+(a_n+1)/10^n]$. So as You ask for algebraic numbers, it may represent every algebraic number within this interval.

The other way to look at is is to use Stern-Brocot tree which is by means of continued fraction $A=[b_0;b_1,b_2,...,b_k]$ for some k. Then number A represents the whole tree when A is a root of it, and every branch of this tree, finite or infinite represents some number. It is interesting, that there You may say that every possible subtree with root in A may be represented by sequences of turns like $LLRRLLLLRLRLLR...$ (XX) on the tree, where R means right, and L means left, finite or infinite. There are interesting relation to Minkowski question mark function and Cantor function.

Then if I understand right, it is possible to reformulate Your question and say that You are asking for algebraic numbers represented within given interval or represented by certain sequences within giver family of sequences like (XX).

As You may see subtree of Stern-Brockot tree is isomorphic to the whole tree, and it is obvious that within given interval You may find infinite number of algebraic numbers. So in fact if You will see any pattern for algebraic number in given interval ( given with some procession) then You may reformulate it as property of whole set of algebraic numbers. And up to Your question: within given interval there is infinite subset of algebraic numbers with any computational complexity. That is because within subtree of Stern-Brockot tree there are presented sequences of any Kolmogorov measure You may think of. Stating finite precision, in fact You give some very beginning sequence in a tree, but not the infinite possible rest.

Interesting case is to ask if there exists any patterns for S-B tree or for any other (decimal, hexadecimal etc) representation for a numbers which may give us insight into property of numbers ( there are some, such simple as divisibility by 2 for example or much more complicated). For example is there any property in any representation ( possibly effective, not straight from the definition of algebraic number) which allows us to say that given number is algebraic, or algebraic of specified kind. Is far as I know there is no pattern in continued fractions coefficients for algebraic number, although, You may find pattern in numbers which are roots of quadratic diofantine equations. So Your question in general has no answer,but there are some patterns in known representations of numbers which gives us some classes of algebraic numbers: for example quadratic one. Maybe someday someone will find other patterns/representations which provide us other possibilities...

Every answer before points You into algebraic complexity theory which is very fashionable today. I would like to try to point in some other direction, which probably is not what You are looking for, but is in my opinion interesting. I have hope that other than usual look is interesting and is not just misinterpretation of Your question.

Say I'm given some finite precision complex number, which I'm told is algebraic over \mathbb{Q}. Is there some well defined notion of arithmetic complexity which can allow me to deduce exactly what algebraic number this finite precision number represents?

Finite precision number is rational number. Then it has finite representation as continued fraction or as decimal number with finite number of digits. Say last digit is $a_n$ which means that we know Your number as $A=...a_0 + a_1/10 + a_2/10^2+... + a_n/10^n$ Then as You may see from decimal representation such number represents whole interval $I=[A,A+(a_n+1)/10^n]$. So as You ask for algebraic numbers, it may represent every algebraic number within this interval.

The other way to look at is is to use Stern-Brocot tree which is by means of continued fraction $A=[b_0;b_1,b_2,...,b_k]$ for some k. Then number A represents the whole tree when A is a root of it, and every branch of this tree, finite or infinite represents some number. It is interesting, that there You may say that every possible subtree with root in A may be represented by sequences of turns like $LLRRLLLLRLRLLR...$ (XX) on the tree, where R means right, and L means left, finite or infinite. There are interesting relation to Minkowski question mark function and Cantor function.

Then if I understand right, it is possible to reformulate Your question and say that You are asking for algebraic numbers represented within given interval or represented by certain sequences within giver family of sequences like (XX).

As You may see subtree of Stern-Brockot tree is isomorphic to the whole tree, and it is obvious that within given interval You may find infinite number of algebraic numbers. So in fact if You will see any pattern for algebraic number in given interval ( given with some procession) then You may reformulate it as property of whole set of algebraic numbers. And up to Your question: within given interval there is infinite subset of algebraic numbers with any computational complexity. That is because within subtree of Stern-Brockot tree there are presented sequences of any Kolmogorov measure You may think of. Stating finite precision, in fact You give some very beginning sequence in a tree, but not the infinite possible rest.

Interesting case is to ask if there exists any patterns for S-B tree or for any other (decimal, hexadecimal etc) representation for a numbers which may give us insight into property of numbers ( there are some, such simple as divisibility by 2 for example or much more complicated). For example is there any property in any representation ( possibly effective, not straight from the definition of algebraic number) which allows us to say that given number is algebraic, or algebraic of specified kind. Is far as I know there is no pattern in continued fractions coefficients for algebraic number, although, You may find pattern in numbers which are roots of quadratic diofantine equations. So Your question in general has no answer,but there are some patterns in known representations of numbers which gives us some classes of algebraic numbers: for example quadratic one. Maybe someday someone will find other patterns/representations which provide us other possibilities...