Base change notation

[franktaw at netscape.net]

Apparently, nobody but Marc and myself cares about this.  At least, 
nobody else has responded.

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