half-baked generalized convolution sequence transforms

[Marc LeBrun]

This is kind of long, but I thought you might find this interesting. It 
kind of fugues off Sloane's "My Favorite Integer Sequences", perhaps in 
some novel directions.

Apologies that this is so half-baked, despite it length.  I'm completely 
awash in new sequences.  Sorry if this is a bit rushed (and maybe 
buggy!).  Hopefully the sectionizing helps.  SeqFreqs, please dive in!


0. Most generally, a sequence S can be transformed by multiplying by a 
matrix M, resulting in a new sequence R.  We like Ms so that R is integral 
whenever S is.  And 1/M gives us the inverse transform, when it exists, and 
is integral.  (I only mention this since many things below can be referred 
back to structural properties of M).


1. A (vanilla) convolution transform specializes M by defining the matrix 
with a single transform sequence T via

   M[i,j]  =  T[j - i]

(typically T[n < 1]=0, so M is lower-triangular, and T[1]=1 so the diagonal 
is integral, etc).  Thus

   R[j]  =  sum S[i] T[j - i]

and we can say R is the T-convolution transform of S.

Interesting transforms typically have an inverse, defined by another 
convolution sequence U.


2. For example if T is the "all 1s" sequence A00012 then the convolution is 
the partial sum transform (PSUM) and U, the inverse first-difference 
transform (DIFF), is simply the convolution with

   1,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,...

(which doesn't seem to be in the EIS, except perhaps as a signed form of 
A019590!<;-).


3. Convolution operators give us zillions of potentially interesting 
identities because they connect sequences in algebraic triples.  So we can 
convolve any two given sequences to get a new sequence, or solve for the 
transform sequence joining two known sequences.  We can also find certain 
special sequences for a given transform, such as the eigensequences.


4. An interesting class of transform sequences are the characteristic 
functions, consisting only of 0s and 1s.

There are a few examples of these convolutions in the EIS, for example 
A006463, "Convolve natural numbers with characteristic function of 
triangular numbers":

   1,2,4,6,8,11,14,17,20,24,28,32,36,40,45,50,55,60,65,70,76,...

They often have nice interpretations such as here, "Length of longest 
maximal chain in partition lattice".

Note that as sequences characteristic functions just define a predicate on 
n (such as "n is triangular") but the transform matrix can be seen as a 
relation between i and j (such as "i and j differ by a triangle").

The inverses of characteristic sequences typically consist of only 0s, 1s 
and -1s, with the sign being the necessary parity to detangle the 
overlapping summands.


5. Now we generalize the vanilla convolution by replacing the index 
subtraction that appears in the summation

   j - i

with some other operation

   j ~ i

(which I pronounce as "the complement of i in j") giving

   R[j]  =  sum S[i] T[j ~ i].


6. It seems (half-bakedly, can you prove it?) that the new operation should 
obey a kind of "reflection" law

   n ~ i = j  <==>  n ~ j = i

This defines what I call a "numbral subtraction",

   [j] - [i]  =  [j ~ i].


7. But the new operation need not be defined for all i,j.  When it's only 
defined for some pairs we can either think of it as an ordinary transform 
with zeros for the undefined pairs, or as a convolution with a special kind 
of sum that's "taken over the complements".


8. The classic example of this generalization is when the "numbral 
subtraction" operation is ordinary integer division.  This is used to 
define the Mobius transform pair.

For the Mobius transform we can say the characteristic function is "all 1s" 
with the summation taken over divisors.  Alternatively, we could say the 
transform matrix gives the integral divisibility relation: 1 just if j/i is 
exactly an integer, else 0.

The inverse sequence is the Mobius mu function, with, as you know, many 
convolution identities involving this transform represented in the EIS.


9. But the "over divisors" convolution isn't limited to this sequence pair!

For example we can factor Mobius's mu into Liouville's lambda, A008836, and 
the characteristic function for squarefree numbers, call it chi(n), so that

   mu(n)  =  lambda(n) chi(n)

These form a "Liouville transform pair", with its own set of 
identities.  For example applying the Liouville lambda transform to "all 
1s" hit on the known sequence A001615

   1,3,4,6,6,12,8,12,12,18,12,24,14,24,24,24,18,36,20,36,32,36,...

"Primitive sublattices of index n in generic 2-dimensional lattice; also 
index of GAMMA_0(n) in SL_2(Z)", whereas applying the Liouville chi 
transform to n produced the new sequence A061020

   1,1,2,3,4,2,6,5,7,4,10,6,12,6,8,11,16,7,18,12,12,10,22,10,...

"Negate primes in factorizations of divisors of n, then sum.", vandalizing 
the classic sum-of-divisors sigma function.

Following the Mobius convention we would call the characteristic chi 
transform the direct Liouville transform and the its signed lambda opposite 
the inverse Liouville transform, although this convention begins to fray on 
sequences with more variegated terms.

Because of the strong relation to Mobius some "crosslinks" show up with the 
Liouville identities.  However I believe the Mobius and Liouville "over 
divisors" transforms are as independent as any two vanilla convolutions (am 
I right?)

Naturally there's Liouville eigensequences too (I've mislaid them just now, 
sorry).


10. But now here's a completely different generalized convolution transform 
using binary bitwise operations (switching to 1-based instead of 0-based 
indexing).

Let's say that j "masks" i just when

   i AND j  =  i

or, equivalently,

   i IOR j  =  j.

Here the complement of i in j is just the ordinary difference--but only 
when j masks i is it defined!  So instead of summing over divisors we sum 
over "bivisors" (or whatever you want to call the binary "maskees").

Using this new template, a direct transform using "all 1s" has an inverse 
transform which is the sequence

       t(n)
   (-1)

where t(n) is A010060, the Thue-Morse sequence

   0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,...

(I think this signed sequence itself is also in EIS...but just try 
searching for signed forms
of the all 1s sequence without going blind!)


11. Applying the direct Thue-Morse "mask" transform to the all 1s sequence 
gives A001316

   1,2,2,4,2,4,4,8,2,4,4,8,4,8,8,16,2,4,4,8,4,8,8,16,4,8,8,16,...

"Gould's sequence: Sum_{k=0..n} (C(n,k) mod 2).". which also could be 
described  as "2 to the number of 1 bits in n".

The inverse transform applied to the natural numbers hits on A060146

   0,1,2,0,4,0,0,0,8,0,0,0,0,0,0,0,16,0,0,0,0,0,0,0,0,0,0,0,0,...

"Nim-Binomial transform of the natural numbers"...so I guess we have 
another name for this transform!  (This sequence was recently added on 
March 6 by John W. Layman--anyone familiar with this work?)

Applying the mask transform to the natural numbers gives the new sequence

   0,1,2,6,4,10,12,28,8,18,20,44,24,52,56,120,16,34,36,76,40,84,88,...

The left-shifting eigensequence of the Thue-Morse transform is kind of 
intriguing

   1,1,2,3,7,8,17,27,66,67,135,204,479,553,1182,1889,4641,4642,9285,...

(for a good time, compare with its first difference!<;-)

This transfrom somewhat counter-intuitively connects three sequences in a 
chain: from A006519 "Highest power of 2 dividing n." to A053644 "Largest 
power of 2 less than or equal to n" to A048678 "Binary expansion of 
nonnegative integers expanded to Zeckendorffian format with rewrite rules 
0->0, 1->01." (jumping between the rightmost, leftmost and middlemost 1 bits).

The Gray Code A003188 has an interesting transform whose only non-zero 
members are 1x and 3x the powers of 2... and so on, ad infinitem (including 
other transforms defined on this same template).


12. The "mask complement" can be interpreted in interesting ways, such as 
subsets.  It is also related in a numbral way to the divisor complement: 
assign the bits to powers of primes.

Note that this is an exact but abstract numbral correspondence: nothing 
says which bits go with which factors, nor that "primes" are the ordinary 
rational primes.

Anyhow, there's some kind of mysterious kinship between these two 
convolution templates.


13. We can, and probably should, invent other transforms along these 
lines.  Of course once we do there's a plethora of new sequences to 
generate and existing sequences to relate.


14. You can also mess around with the "sum" operator etc in the convolution 
template, substituting any other suitable kind of arithmetic, say bitwise 
operations (XOR looks interesting).  All those weird numbral systems (base 
sqrt(2), Zeckendorf, etc etc) are also possible.


15. We can generate tons of new sequences for the EIS using the ideas here, 
but how the heck would we describe them succinctly?  We need to be able to 
point at something defining the "Thue-Morse mask transform" or whatever.

So, anyone want to collaborate on this?  We might
   write this stuff up for submission to the JIS
   generate new sequences
   systematically look for hits using new transforms
   extend the transform library

If you're interested, please let me know...
Thanks!