[seqfan] Re: A new (or old), encompassing definition of Integer Sequences.

Antti Karttunen antti.karttunen at gmail.com
Mon Feb 11 20:33:24 CET 2013


> Date: Mon, 11 Feb 2013 11:29:34 -0400
> From: Maximilian Hasler <maximilian.hasler at gmail.com>
> To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
> Subject: [seqfan] Re: A new (or old),   encompassing definition of
>         Integer Sequences.
> Message-ID:
>         <CAOPi3Q+Lja4T_ZGJaedECVSYP6Z2+uAyApSEppJ0zfzuq2vJzA at mail.gmail.com>
> Content-Type: text/plain; charset=ISO-8859-1
>
> On Sun, Feb 10, 2013 at 4:39 PM, Antti Karttunen
> <antti.karttunen at gmail.com> wrote:
>> An integer sequence is a function Z -> Z (usually partial),
>> whose domain (*) is defined by an integer sequence.
>
> I don't like that too much...

Well, I started disliking it also, but maybe for other reasons than you.

> That's much "noise" / big machinery, mainly to deal with a tiny offset
> adjustment
> (I know you also think of "holes" in the domain, but see below...)
>
> In addition, it is ill defined (through an infinite recursion)... ;-) !

Not necessarily, as any restriction of id: n -> n on Z works
as a sequence defining its own domain. Examples: whole Z, the
non-negative integers (A001477), the naturals (A000027),
and also the empty sequence/set [] (call that A000000 if you wish),
which defines a function which is nowhere defined (for example,
because it never halts), which as a sequence, is that empty sequence
itself.

Then, clearly, we have both A001477 and A000027 as domains for many,
many sequences which are known to have infinite number of terms.

However, I was daydreaming about having some magical, hypothetical,
"semi-oracular" sequence telling for example, how many more Fermat
primes ( A019434 ) or other rare numbers we should expect to exist,
without actually knowing what they are, but after a moment's
reflection, I realized that this is the same thing, as _in principle_
knowing what those terms are. (I.e. just iterate from the last known
value onward and test. Don't care about the time it takes, the time
doesn't exist, they say.)

So, after founding myself knee-deep in the recursion theory,
(e.g. http://en.wikipedia.org/wiki/Recursively_enumerable_set
from which page an important point: "The definition of a recursively
enumerable set as the domain of a partial function, rather than the
range of a total recursive function, is common in contemporary
texts.")

and thinking about the case https://oeis.org/A210439
("The minimal Skewes number for prime n-tuplets"),

where similarly, in principle n=1 belongs to the domain of this
function, and in principle, we know _not just that_ it exists, but _we
have_ even a simple recipe for finding it (again: "just iterate"), but
in practice
it cannot be known for a moment, possibly for many decades to come.
(BTW, note how its magnitude (the current estimate's) is about the
same as RSA-1024 semiprime's).

So, I started to doubt whether such a "God's view" of mathematics is
of any real help, when designing a formalism for storing temporal
facts into an actual, physical database.
Temporal in a sense, that although the sequences themselves might be
timeless platonic objects, our knowledge about them is still limited
by the computer execution time and other physical constraints.
See also, Doron Zeilberger's "How real is Ω (Omega)" on page 2 of his
http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/enquiry.pdf


>
>
>> (* in the first sense given in
>> http://en.wikipedia.org/wiki/Partial_function : "Most mathematicians,
>> including recursion theorists, use the term "domain of f" for the set
>> of all values x such that f(x) is defined.")
>
> here I totally agree, not much doubt...
>
>
>> How about that?
>>
>> Why so general? Then we can include also David Wilson's idea from
>> 1999: http://list.seqfan.eu/pipermail/seqfan/2012-March/009214.html
>>
>> Actually, now that I re-read it, it seems that his "index sequences"
>> is just the same as what I mean by the domain sequence here.
>
> well, yes and no...
> If you define:
> "a subset of the integers [bounded from below] is a strictly
> increasing sequence"
> then one could argue that it might be the same,
> but the philosophy is a bit different ; requiring a "sequence" instead
> of a domain implies a re-indexing of the original sequence..
>
> In that sense, it is not "so general" but rather restrictive:
> instead of allowing sequences with holes, you impose in some sense
> that only integer sequences defined on IN = {1,2,3...} are allowed,
> and if this is not the case a priori,
> then the "faulty" sequence must be redefined to be the composition of
> itself with the sequence listing its domain by indexing it with IN
> ...
>
>
>> Note that the domains of the most infinite sequences in OEIS
>> have currently been defined with either A001477 or A000027.
>> (or with their characteristic functions on Z, if you so wish.)
>
> yes and no (again);
> there are many many sequences of the form
> "a(n) = [some property] of the n-th prime"
> or similar.
> In your philosophy, should this be "forbidden" in favour of defining
> that sequence
> as a sequence defined "on the primes only" ?
> i.e., "a(p) = [some property] of the prime p"
> and be re-indexed by the sequence A40 (the primes) ?

No, not really. I am not myself so keen of sequences with holes in
their domains (of which an example in David Wilson's original 1999
mail of a function which is defined only for square-free numbers
A005117).
However, I thought that it would be nice if the formalism would allow
implementing of such functions later (if deemed necessary), as well as
functions defined on whole Z (like function abs, or Fibonacci numbers
whose domain has been extended also to negative numbers, where F_{-n}
= (-1)^(n+1) * F_n. There are also other examples in OEIS, usually
simple polynomes, that can be easily and unambiguously extended to the
negative side.)

But here the boon and curse is the very inclusive nature of OEIS.
A curse when trying to draft a clean, nice definition for a sequence,
a boon because it allows such diverse material.

Like the sequence
http://oeis.org/A134204
of which it is certainly not known whether it is infinite or not,
but at least, the case is immediately clear if an a(n) dividing n+1
is found.
So, it should be obvious that these sequences belong to a class of
sequences "whose domain defines their own domain", which surely is
even more tautological than my original definition, where I was
thinking other sequence's range defining other sequence's domain.
So, maybe we should ditch that.

But I guess we should grok this:
http://en.wikibooks.org/wiki/Haskell/Denotational_semantics#.E2.8A.A5_Bottom

and maybe, instead of defining "bottom" as "completely undefined
value", interpret it just as "currently undefined value". Where would
that lead us?


Yours,

Antti

>
> Maximilian



More information about the SeqFan mailing list