Base change notation
franktaw at netscape.net
franktaw at netscape.net
Thu Aug 3 03:39:37 CEST 2006
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
More information about the SeqFan
mailing list