Base change notation

[Jonathan Post]

Dear Frank,

My apology for not responding sooner.  My wife has been tied up in trying to
fly from Great Britain back to the USA.

Yes, I care quite a lot about this, and have read and pondered your
ingenious notation.  I've submitted at least a dozen seqs that could be
better described, or at least commeneted, with your notation.  I think I'd
calculated one more that hadn't been submitted.  Without fumbling through
notes, I think it was primes which are substrings of pi in base e, or
something like that (we'd had some discussions of what was "natural").

Good notation builds clear thoughts, and elegant proofs.

Best,

Jonathan Vos Post

>
>
> Anybody?
>
> Franklin T. Adams-Watters
>
>
> -----Original Message-----
> From: franktaw at netscape.net
>
> From: Marc LeBrun <mlb at well.com>
> >
> > Apologies for the length of this response, but this is a subject I've
> devoted a lot of time and thought to. Thanks in advance >for your
> patience...
> >
> > >=franktaw at netscape.net
> > > I really don't like the base change notation that is used for a
> number of OEIS entries.
> >
> > Well, there's of course no accounting for taste, but please let me
> assure you a considerable amount of time and effort were >expended
> arriving at that notation.
> >
> > It's far from a gratuitous choice, although there may be aspects of
> its full intended usage that may not be immediately >apparent (and
> which admittedly haven't been adequately documented). I will try to
> explain some of this below.
> >
> > By the way, I corresponded with a number of people regarding this
> notation before adopting it, including Don Knuth, who >appreciated its
> motivations and didn't find it objectionable. (I was particularly
> concerned by its possible collision with his use of >brackets to denote
> extraction of power series coefficients).
> >
> > In addition there was a certain amount of eMail back-and-forth with
> NJAS and others on the seqfan list to make sure it was >reasonably
> acceptable before I started using it in OEIS entries.
> >
> > So at this point it's become a little bit established by common
> usage. Maybe it just needs more documentation somewhere?
>
> I haven't said anything until now for precisely this reason. And
> perhaps this consideration trumps all the others. But my dislike of the
> notation recently boiled over, so let me make my case.
>
> I regret that I wasn't involved when this discussion took place, but
> that's water under the dam now.
>
> > All this is not to say we can't change it if the consensus is reached
> that it's in fact a bad idea. But I'd at least hope this is >done with
> due consideration for its origins.
> >
> > > This involves writing:
> > > (b) [n] (c),
> > > meaning "write n in base b, and reinterpret as base c".
> >
> > That's a good but rough gloss, useful for quickly describing many
> simple cases, such as 4[n]2, aka A000695, which also >happens to
> contain a somewhat lengthy comment (for an OEIS entry) on the notation.
> I will try to recap some of the >genesis here.
> >
> > 1. Strings versus integers.
>
> I have elided this section, as I agree with it entirely.
>
> > 2. Bases, subscripts and ASCII
> >
> > In trying to come up with a concise, ASCII-friendly, notation, one
> issue I struggled mightily with was the schoolbook >convention of
> denoting the base of a numeral-string via a subscript. Of course the
> most common ASCII convention for writing >a subscript is brackets [.],
>
> However, subscripts in the OEIS are usually written a_n, not a[n].
>
> >so that, for example, one might write
> >
> > 101[2] = 5[10]
> >
> > However I couldn't figure out how to make this jibe with that key
> values-not-strings interpretation, nor work well for >notating
> sequences involving rebasing. For example, describing A007088 as
> something like
> >
> > a(n) = (n[2])[10]
> >
> > drags us back into the morass of expressions on strings versus
> numerical values, and is a confusing clutter with a very high
> >punctuation to content ratio.
> >
> > 3. Indexing, Polynomials and Algebra
> >
> > Fortunately the much more common usage of subscripts to indicate
> indexing suggested a happy alternative. It is typical to >write, say,
> S[n] to denote the n-th member of some sequence of objects S.
> >
> > Indeed, when we write, say, 691, it is a compression of the expansion
> >
> > 6 * 10^2 + 9 * 10^1 + 1 * 10^0.
> >
> > Moreover, consider "the set of polynomials with non-negative
> coefficients less than ten"; call it Z10. Then, in the natural
> >ordering, the 691st element of this sequence would be written
> Z10[691].
>
> This is another notational novelty, with its own opportunities for
> confusion. Seeing Z10, my first reaction is to think the author meant
> Z_10, the integers mod 10, aka Z/10Z. (Z_10 is also used in the
> literature for fractions a/b where gcd(b,10) = 1.)
>
> It also looks like maybe it should be [Z10], a reference to the
> bibliography.
>
> > And of course this generalizes readily to "other values of 10", such
> as Z2, "the set of polynomials with non-negative >coefficients less
> than two", and so on. Z2[691] is a ninth-degree polynomial, while
> Z10[691] is quadratic.
> >
> > Now the convention for denoting function application is to write the
> actual parameter immediately to the right. It is >optionally
> parenthesized if needed for clarity, but there are many subjects (eg
> lambda calculus) where simple concatenation is >the default.
> >
> > So to map our 691st polynomial Z10[691] back into an integer, we
> merely apply it to the value 10 (aka "evaluated at >x=10"--but that way
> of putting it introduces the needless new entity "x") which can be
> written out in full as
> >
> > Z10[691](10) = 691
> >
> > or more concisely as
> >
> > Z10[691]10 = 691
> >
> > or, dropping the "Z" (which I'll try to justify further below)
> >
> > 10[691]10 = 691
> >
> > which can be generalized to the identity
> >
> > b[n]b = n
> >
> > Suggesting, for example, more algebraic ideas, such as b[n]q being
> (approximately) the inverse of q[n]b.
>
> I don't think my versions of these are in any way inferior:
>
> n_{b->b} = n
>
> and n_{b->q} is (approximately) the inverse of n_{q->b}.
>
> > The key general idea is that the brackets suggest indexing. And then
> we simplify the "base" arguments to expose other >relationships as much
> as possible.
> >
> > But writing 2[n]10 is merely a slightly abbreviated alternative to
> the more obscure and verbose Z2[n](10).
> >
> > And, for example, (1/p)[.]p has a natural symmetry with p[.](1/p), so
> why needlessly clutter up one side more than the >other?
> >
> > Note that b[n]q represents a mapping from numbers to numbers, without
> the need to invoke "string" concepts.
>
> Elided, not a difference between the notations.
>
> > 4. Object-oriented ("numbral") arithmetic
> >
> > More radically, the indexing interpretation doesn't constrain b to be
> a numerical "base" at all--it can be a more general "basis" >whose
> elements follow some different algebra, such as GF2. This allows us to
> encode its elements as GF2[n]2 so as to be able >to refer to them in
> OEIS sequences, and to write identities such as
> >
> > (GF2[n]^2)2 = Z2[n]4 (*)
>
> But GF2 to mean "the sequence of polynomials with coefficients in GF(2)
> is *another* novelty, and likewise subject to confusion.
>
> > where the types of the subexpressions are clear as is their
> applicative evaluation (a la lambda calculus)...
> >
> > ...but I'll spare you that digression, and try to address the other
> points:
> >
> > > The main problem is that it is not distinctive enough; it looks
> like it means b*n*c.
> >
> > Perhaps only if you're in the habit of thinking of []s as being
> equivalent to ()s. While in some contexts that's done, in
> >typographically starved ASCII it's not all that usual--often []s are
> interpreted very differently than ()s.
>
> I'm a programmer, quite familiar with such conventions - it still looks
> like multiplication to me.
>
> > > Also, the "n" in the center can get a bit lost.
> >
> > Yes, I can sympathize with that. But it's just as often the case in
> the OEIS that the "n" is just a running index anyway. If >the "b" and
> "q" are just numbers, then it stands out by being a letter. In fancier
> formulas any or all of the three might be >complicated.
> >
> > > Instead, I propose writing:
> > > n_{b->c}.
> > > This avoids both problems I described above; and it is clear enough
> that I think someone might guess what it means.
>
> In my mind, this is the strongest point in its favor. I don't think
> anyone not already familiar with the b[n]c notation would guess what it
> means.
>
> > > (The "->" of course represents an arrow, which is what would be
> used if writing by hand or if typesetting.)
> >
> > This is certainly an alternative, which I'd consider if all I ever
> wanted to do is convert between numerical bases. But I'd be >sad to
> lose all those other interesting allusions. Writing
> >
> > n_{GF2->2}
> >
> > seems more cluttered and confusing to me,
>
> It doesn't to me.
>
> >and I can't see how to use it to write the above identity (*) which
> expresses that "A000695 encodes the squares of GF2".
>
> Try
>
> (n_{2->GF2})^2_{GF2->2} = n_{2->4}.
>
> It's a little more verbose, but in incorporates the idea that writing n
> as a polynomial in GF(2) involves its binary representation, a fact
> that is lost in your version.
>
> This notation can also be used for general substitutions:
>
> (x^2+x+1)_{x->y-1} = y^2-y+1.
>
> In mathematical logic, this is sometimes written something like
>
> (x^2+x+1) [y-1/x] = y^2-y+1
>
> (more often with logical formulas than arithmetic expressions); but
> using this more generally is also likely to be confusing.
>
> > But, as there's no accounting for taste, I will happily defer to
> whatever NJAS and the OEIS community prefers.
>
> As will I, of course.
>
> Frank Adams-Watters
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20060816/96451e9a/attachment-0003.htm>