[seqfan] Re: structure & sequences defined by "exotic multiplication"

[Jonathan Post]

Sorry, I know it's too soon to email again, butI missed what I meant
to say also:

A023814  Number of associative binary operations on an n-set; number
of labeled semigroups.

On Wed, Dec 23, 2009 at 6:20 PM, Jonathan Post <jvospost3 at gmail.com> wrote:
> I like what Maximilian shows here.
>
> As to the original question, "Rabi and Sherman (1997) show that no
> total, associative function defined over a universe having at least
> two elements is one-to-one."
>
> Tight lower bounds on the ambiguity of strong, total, associative,
> one-way functions
> Christopher M. Homan
> Journal of Computer and System Sciences
> Volume 68, Issue 3, May 2004, Pages 657-674
>
> On Wed, Dec 23, 2009 at 6:08 PM, Maximilian Hasler
> <maximilian.hasler at gmail.com> wrote:
>>> the sequence may be more interesting if "o" were associative, is there a
>>> list of binary associative functions?
>>
>> I had an idea for an "exotic" associative operation ;
>> it's based on a very simple idea, so I expect it to be studied
>> somewhere, but as far as I can recall, I never heard of it.
>>
>> The idea is to consider the bijection of positive integers (or fractions)
>> with polynomials of [nonnegative] integer coefficients :
>>
>> n = product( p_i ^ e_i )  <-->  P_n = sum( e_i * X^i )
>>
>> (where we should probably number the primes starting from 0 on:
>> p_0 = 2, p_1 = 3, ...)
>>
>> Then addition of these polynomials corresponds to multiplication of numbers
>> ( P_{mn} = P_m + P_n )
>> while multiplication of polynomials (convolution product) is the new
>> operation @,
>>  P_m * P_n =: P_{ m @ n }
>>
>> Or otherwise said, if m = product( p_i ^ f_i ),
>>
>> m @ n = product( p_k ^ (sum_{i=0..k} e_{k-i} * f_i)
>>
>>
>> Then we have commutativity and associativity of @,
>> and distributivity of @ over * :
>> k @ (m * n) = ( k @ m ) * ( k @ n ).
>>
>> The prime 2 (corresp. to polynomial X^0) is the neutral element for @,
>> and repeated composition of 3 will yield all primes :
>> 3 @ 3 (=: 3 ^^ 2) = 5
>> 5 @ 3 (= 3 ^^ 3) = 7
>> 7 @ 3 (= 3 ^^ 4) = 11
>> etc.
>>
>> I think it could be worth while studying the structure resulting from
>> this operation
>> (it turns the multiplicative group of fractions into a ring)
>> in particular in the context of multiplicative functions.
>>
>> Of course this operation also leads to some new sequences. Obviously,
>> @-multiplication by a prime just corresponds to shifting the prime
>> factors to the n-th subsequent prime.
>>
>> n @ 3 : (= A003961 : multiplicative with a(p(k)) = p(k+1))
>> 1, 3, 5, 9, 7, 15, 11, 27, 25, 21, 13, 45, 17, 33, 35, 81, 19, 75, 23,
>> 63, 55, 39, 29, 135, 49, 51, 125, 99, 31, 105, ...
>>
>> n @ 4 : amounts to taking squares (exponents of prime factors are doubled)
>>
>> n @ 5 : (= A045966 except for the initial term)
>> 1, 5, 7, 25, 11, 35, 13, 125, 49, 55, 17, 175, 19, 65, 77, 625, 23,
>> 245, 29, 275, 91, 85, 31, 875, 121, 95, 343, 325, 37, 385,...
>>
>> n @ 6 : (not in OEIS)
>> 1, 6, 15, 36, 35, 90, 77, 216, 225, 210, 143, 540, 221, 462, 525,
>> 1296, 323, 1350, 437, 1260, 1155, 858, 667, 3240, 1225, 1326, 3375,
>> 2772, 899, 3150, ...
>>
>> less trivial : n ^^ 2 = n @ n : (not yet in OEIS).
>>
>> 1, 2, 5, 16, 11, 90, 17, 512, 625, 550, 23, 6480, 31, 1666, 2695,
>> 65536, 41, 101250, 47, 110000, 10285, 5566, 59, 1866240, 14641, 10478,
>> 1953125, 653072, 67, 1212750
>>
>> etc... (n ^^ 3, ...)
>>
>> But once again, I suspect this has already been studied.
>> Does anyone know about this, or have a reference ?
>>
>> Regards,
>> Maximilian
>>
>>
>> _______________________________________________
>>
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>