Omni-transcental numbers
Robert Kolker
sequence of (decimal) digits, that sequence appears somewhere in the
decimal expansion of the number.
Question: Are there any omni-transcendtal numbers.
Another question. Has this question been addressed in the literature
anywhere?
I coined the term omni-transcendental for want of a better name. If you
can think of a better name, by all means propose it.
Bob Kolker
Arturo Magidin
Robert Kolker <bobk...@attbi.com> wrote:
>Call a number omni-transcendental if and only if, give any finite
>sequence of (decimal) digits, that sequence appears somewhere in the
>decimal expansion of the number.
>
>Question: Are there any omni-transcendtal numbers.
Yes. For example,
.0123456790001020304...9899000001002003...9989990000...
the number whose decimal expansion lists all finite sequences of
digits in order, where two finite sequences of digits s_1 and t_1
satisfy
s_1 <= t_1 if and only if length(s_1)< length(t_1) or
length(s_1)=length(t_1) and s_1<=t_1 in the lexicographic order, with
0<1<2<...<9.
Also, every normal number will satisfy this condition.
>Another question. Has this question been addressed in the literature
>anywhere?
Don't know, but it seems like a natural question to ask related to
normal numbers, so I would start there.
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes")
======================================================================
Arturo Magidin
mag...@math.berkeley.edu
Nemo
> Call a number omni-transcendental if and only if, give any finite
> sequence of (decimal) digits, that sequence appears somewhere in the
> decimal expansion of the number.
>
> Question: Are there any omni-transcendtal numbers.
>
> Another question. Has this question been addressed in the literature
> anywhere?
>
This question specifically --- no, because it's too easy.
Many related questions have been addressed in the research on formal
languages (or more precisely formal languages over infinite words).
Type "infinite words" into Google.
Nemo
Nick Oosterhof
> Call a number omni-transcendental if and only if, give any finite
> sequence of (decimal) digits, that sequence appears somewhere in the
> decimal expansion of the number.
>
> Question: Are there any omni-transcendtal numbers.
Yes there are. [1] gives an example: simply enumerate all natural numbers in
their order and 'concatenate': 0.12345678910111213...
> Another question. Has this question been addressed in the literature
> anywhere?
Yes, even more complicated questions have been addressed. [1] gives:
"A real number x is normal in base b if in its representation in base b all
digits occur, in an asymptotic sense, equally often. In addition, for each
m, the b^m different m-strings must occur equally often."
There are many normal numbers, although an example of a normal number in
each base is still to be found.
The normalness of pi is yet unknown.
Nick
Robert Kolker
Nemo wrote:
>
> Many related questions have been addressed in the research on formal
> languages (or more precisely formal languages over infinite words).
>
> Type "infinite words" into Google.
A word is a finite sequence of letters from some alphabet (or the empty
word). I do not see how this applies.
Bob Kolker
Robert Kolker
Nick Oosterhof wrote:
>
> Yes there are. [1] gives an example: simply enumerate all natural numbers in
> their order and 'concatenate': 0.12345678910111213...
What about the sequence 2468101214 and such like sequences. I do not see
how they occur in this concatenation. Can you clarify a bit.
Bob Kolker
Robert Kolker
Robert Kolker wrote:
Oh Duh! Never mind. I was a bit slow on my feet.
Bob Kolker
Gerry Myerson
=> Call a number omni-transcendental if and only if, give any finite
=> sequence of (decimal) digits, that sequence appears somewhere in the
=> decimal expansion of the number.
No, don't call such a number omni-transcendental, because customary
use of English would require that omni-transcendental numbers be
transcendental numbers, and I doubt that they all are. E.g., it is
widely believed that square root of two has the property you
describe, but it is algebraic, not transcendental.
=> I coined the term omni-transcendental for want of a better name. If
=> you can think of a better name, by all means propose it.
Quasi-normal? Normalish? All-inclusive?
--
Gerry Myerson (ge...@mpce.mq.edi.ai) (i -> u for email)
Robert Kolker
Gerry Myerson wrote:
> Quasi-normal? Normalish? All-inclusive?
>
Quasinormal wins in a thrice. Good choice.
Bob Kolker
Nemo
An infinite word is an infinite sequence of letters from some alphabet.
Nemo
David W. Cantrell
??? Unless you're punning (based on the fact that GM had listed three
possibilities), the correct phrase is "in a trice".
David
Gus Gassmann
Arturo Magidin wrote:
> In article <3E5299DD...@attbi.com>,
> Robert Kolker <bobk...@attbi.com> wrote:
> >Call a number omni-transcendental if and only if, give any finite
> >sequence of (decimal) digits, that sequence appears somewhere in the
> >decimal expansion of the number.
> >
> >Question: Are there any omni-transcendtal numbers.
>
> Yes. For example,
>
> .0123456790001020304...9899000001002003...9989990000...
>
> the number whose decimal expansion lists all finite sequences of
> digits in order, where two finite sequences of digits s_1 and t_1
> satisfy
>
> s_1 <= t_1 if and only if length(s_1)< length(t_1) or
> length(s_1)=length(t_1) and s_1<=t_1 in the lexicographic order, with
> 0<1<2<...<9.
>
> Also, every normal number will satisfy this condition.
Is this true? I thought normality was defined in probabilistic terms,
so that each digit sequence will occur _with probability 1_, which
is not quite the same thing.
Arturo Magidin
It may be a different definition of normality. My understanding of
normality is that a number was normal if its decimal expansion
satisfied, for any given sequence of n digits, that the limit of the
number of occurrences of the sequence in the first m digits was
exactly the expected occurrence, 1/10^n. I.e., that any sequence
occurs with the expected density.
Robert Israel
>Arturo Magidin wrote:
>> In article <3E5299DD...@attbi.com>,
>> Robert Kolker <bobk...@attbi.com> wrote:
>> >Call a number omni-transcendental if and only if, give any finite
>> >sequence of (decimal) digits, that sequence appears somewhere in the
>> >decimal expansion of the number.
Bailey and Crandall would call this "10-dense": see their paper
"Random Generators and Normal Numbers",
<http://www.nersc.gov/~dhbailey/dhbpapers/bcnormal.pdf>
>> Also, every normal number will satisfy this condition.
>Is this true? I thought normality was defined in probabilistic terms,
>so that each digit sequence will occur _with probability 1_, which
>is not quite the same thing.
Normal means each digit sequence occurs with the correct
asymptotic frequency. It's "probabilistic" only in the sense that
we might say a certain event has probability p if
(number of times it occurs in the first n digits)/n -> p as n -> infinity.
So in particular anything that has positive probability in this
sense _must_ occur infinitely many times.
Robert Israel isr...@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2
Gottfried Helms
hmmm, before fixing a choice, it seems to be
reasonable to decide another question:
does the number have any finite sequence
- one time (exactly, at least)
- a certain expected frequency, constant for all
- infinitely often?
The intended use of the phrase "normal" should
be considered *very* careful...
The three additional properties above, problematizing
this, may not be sufficient or even overlap - I didn't
check this, just an impulse.
Gottfried Helms
Dave L. Renfro
[sci.math Feb 18 2003 4:30:30:000PM]
http://mathforum.org/discuss/sci.math/m/483879/483879
wrote
See Section 5 (pp. 13-20) of [1]. Theorem 5.9 on p. 18 of [1]
says that all but a sigma-porous set (see * below) of real numbers
are absolutely disjunctive. Disjunctive to base b (b being some
integer greater than 1) means that every finite b-word appears
infinitely often in the b-ary expansion of the number (note this
is equivalent to every finite b-word appearing at least once), and
the adjective "absolutely" means that this property holds for each
b = 2, 3, ... The result is virtually immediate (although they do
give a careful proof), since for each of the countably many ways
of choosing a fixed b and a fixed b-word, the collection of numbers
whose b-ary expansions don't contain that b-word infinitely often
is a uniform Cantor set, and hence is porous (even uniformly porous;
in fact, even uniformly for the stronger lim-inf type of porosity
that Julia set theorists use). Recall that the larger collection
of numbers which fail to be absolutely normal (or which fail to be
simply normal relative to a specific base) forms a measure zero
(but with Hausdorff dimension 1) co-meager set (see [5] and [6]).
The last few paragraphs of [6] discusses disjunctive real numbers
and includes two references not given here. In [6] I also explain
why including each b-word once is equivalent to including each
b-word infinitely often (this is in regards to Gottfried Helms'
post in this thread).
(*) A subset E of a metric space is called "porous" if locally at
each point of E there exist open balls disjoint from E whose
radii are sufficiently large that the ratios of these radii to
the distance of these balls from the point in question is bounded
above zero. It is immediate that any porous set is nowhere
dense. In fact, this notion is somewhat akin to what one might
call "Lipschitz nowhere dense". The Lebesgue density theorem
implies that any porous set in R^n also has measure zero. Thus,
every sigma-porous set (that is, any countable union of porous
sets) is both meager (i.e. a first category set) and measure
zero. On the other hand, there exist meager sets with measure
zero (indeed, even closed measure zero sets, or even closed
sets having Hausdorff dimension zero) that are not sigma-porous.
The significance of "closed" in the preceding is that every
closed measure zero set in R^n is automatically nowhere dense,
but there exist meager sets with measure zero (even porous sets
with Hausdorff dimension zero) in R^n that cannot be covered by
a countable union of closed measure zero sets. See [4] for
the Hausdorff dimension zero part. For the porous part, use the
argument in [4] along with the fact that every nowhere dense set
in R^n contains a subset that is porous in R^n and is co-meager
relative to that nowhere dense set (for this last fact, see
the paper whose reviews are MR 97j:28004 and Zbl 883.26002).
However, note from what I said earlier that the collection of
numbers that are not absolutely disjunctive is a countable union
of closed porous sets, and hence this collection is small in both
of these ways -- it's small by virtue of being sigma-porous and
it's small by virtue of being a countable union of closed measure
zero sets. None of these remarks, aside from the fact that every
sigma-porous set is a meager set with measure zero, but not
conversely, are mentioned in [1], [2], or [3], which is why I
went into so much detail here.
[1] Cristian S. Calude, Lutz Priese, and Ludwig Staiger,
"Disjunctive Sequences: An Overview", CDMTCS-063 (October 1997),
Centre for Discrete Mathematics and Theoretical Computer
Science, University of Auckland, New Zealand, 39 pages.
An 871 K .pdf file can be found at
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl
[2] Cristian S. Calude and Tudor Zamfirescu, "The typical number
is a lexicon", New Zealand J. Math. 27 (1998), 7-13.
[MR 99f:03086; Zbl 953.03068]
http://www.emis.de:80/cgi-bin/zmen/ZMATH?type=html&an=0953.03068
[3] Cristian S. Calude and Tudor Zamfirescu, "Most numbers obey
no probability laws", Publ. Math. Debrecen 54 (1999), suppl.,
619-623. [MR 2000i:28010; Zbl 981.60013]
http://www.emis.de:80/cgi-bin/zmen/ZMATH?type=html&an=0981.60013
[4] Dave L. Renfro, 01-05-2000 sci.math post "HISTORICAL ESSAY
ON F_SIGMA LEBESGUE NULL SETS".
http://mathforum.org/discuss/sci.math/t/267778
[5] Dave L. Renfro, 16-06-2001 sci.math post on normal numbers.
http://mathforum.org/discuss/sci.math/m/342661/342664
[6] Dave L. Renfro, 05-07-2002 sci.math post on numbers normal
to one base but not to another base.
http://mathforum.org/discuss/sci.math/a/t/422475
Dave L. Renfro
Robert Kolker
Dave L. Renfro wrote:
> [6] Dave L. Renfro, 05-07-2002 sci.math post on numbers normal
> to one base but not to another base.
> http://mathforum.org/discuss/sci.math/a/t/422475
>
>
Good stuff! Thank you.
Bob Kolker
Robert Israel
Gottfried Helms <he...@uni-kassel.de> wrote:
>hmmm, before fixing a choice, it seems to be
>reasonable to decide another question:
>does the number have any finite sequence
> - one time (exactly, at least)
> - a certain expected frequency, constant for all
> - infinitely often?
If every finite sequence occurs at least once, then every finite sequence
must occur infinitely often (you have the sequence S, and S1, and S01, and
S001, etc).
Stephen J. Herschkorn
>
>In article <3E5299DD...@attbi.com>,
>Robert Kolker <bobk...@attbi.com> wrote:
>
>
>>>Call a number omni-transcendental if and only if, give any finite
>>>sequence of (decimal) digits, that sequence appears somewhere in the
>>>decimal expansion of the number.
>>>
>>>Question: Are there any omni-transcendtal numbers.
>>
>>
>
>Yes. For example,
>
>.0123456790001020304...9899000001002003...9989990000...
>
>the number whose decimal expansion lists all finite sequences of
>digits in order, where two finite sequences of digits s_1 and t_1
>satisfy
>
>s_1 <= t_1 if and only if length(s_1)< length(t_1) or
>length(s_1)=length(t_1) and s_1<=t_1 in the lexicographic order, with
>0<1<2<...<9.
>
Let's extend the problem a bit: It is not clear that the above example
has the property that every finite pattern appears at least once in any
integer base representation. That is, we have defined a number which
satisfies the property in decimal representation, but not necessarily in
other bases. Can we prove that it indeed does in all bases? If not,
can we cook up a number which does?
All normal numbers satisfy this extended property. I may be out of
date, but isn't true that, although almost all numbers are normal, no
one has actually shown a specific number to be normal?
--
Stephen J. Herschkorn hers...@rutcor.rutgers.edu
Robert Israel
Stephen J. Herschkorn <hers...@rutcor.rutgers.edu> wrote:
>Let's extend the problem a bit: It is not clear that the above example
>has the property that every finite pattern appears at least once in any
>integer base representation. That is, we have defined a number which
>satisfies the property in decimal representation, but not necessarily in
>other bases. Can we prove that it indeed does in all bases? If not,
>can we cook up a number which does?
>All normal numbers satisfy this extended property. I may be out of
>date, but isn't true that, although almost all numbers are normal, no
>one has actually shown a specific number to be normal?
No. It's actually not that hard to construct one. See my posting in the
thread "sequences of digits with equal frequency" from November 9 2000.
Gottfried Helms
>
> If every finite sequence occurs at least once, then every finite sequence
> must occur infinitely often (you have the sequence S, and S1, and S01, and
> S001, etc).
>
thanks; I assume, this is right, but it's somehow unintuitive to me.
(Hmm. one day I must learn, why I have difficulties with this type of problems)
---
Well, after some considerations...
Another argument based on yours comes to my mind:
If I had one partial sequence S, and assume, it would be occuring
only one time, then all sequences containing it (must be infinitely
many since *all* finite sequences are required) must overlap S
at S' position. We could fix S at the start of the number r, and can have
infinitely many super-sequences *starting* with it.
There must also be infinitely many *ending* with it - so S cannot be
positioned at the left of the digits of r, but must be moved infinitely
far out...
Well, it seems I'm going to catch it, at least partially.....
:-)
Gottfried Helms
Gottfried Helms
>
> Robert Israel schrieb:
> >
> > If every finite sequence occurs at least once, then every finite sequence
> > must occur infinitely often (you have the sequence S, and S1, and S01, and
> > S001, etc).
> >
> thanks; I assume, this is right, but it's somehow unintuitive to me.
> (Hmm. one day I must learn, why I have difficulties with this type of problems)
well, silly. Your argument reflects, S1,S01 cannot overlap, thus I need
infinitely many S. It's just as simple as mine.
--
Well, are these arguments completely equivalent, btw? Sometimes
tiny differences in the arguments make a big difference for the
range, where they are valid...
Gottfried Helms