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

[Jonathan Post]

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/
>