login
Arithmetic derivative of elements of GF(2)[x], evaluated at x=2.
0

%I #10 Mar 24 2024 16:54:48

%S 0,0,1,1,0,0,1,1,4,4,5,1,4,1,5,5,0,0,1,1,0,0,9,14,4,1,15,5,4,8,5,1,16,

%T 28,17,10,16,1,17,5,20,1,21,26,4,20,11,1,16,12,27,17,4,16,17,1,20,5,

%U 13,1,20,1,29,21

%N Arithmetic derivative of elements of GF(2)[x], evaluated at x=2.

%C The indices of this sequence are sorted by evaluation at x=2, i.e. 0, 1, x, x+1, x^2, x^2+1, etc. Generalization of arithmetic derivative is as described by Victor Ufnarovski and Bo Ahlander. For a general UFD this requires a choice of canon primes for which p' = 1. However, GF(2)[x] has only one unit, so there is a unique arithmetic derivative over this UFD.

%C The arithmetic derivative of a square polynomial in GF(2)[x] is 0 so square polynomials act like units: given f, g in GF(2)[x], (f*f*g)' = f*f*(g'). The arithmetic derivative of a positive degree squarefree polynomial in GF(2)[x] is always nonzero.

%H Victor Ufnarovski and Bo Ahlander, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL6/Ufnarovski/ufnarovski.html">How to Differentiate a Number</a>, J. Integer Seqs., Vol. 6, 2003.

%e To find a(9), first convert 9 into its corresponding GF(2) polynomial x^3 + 1. Then find its arithmetic derivative, x^2. Finally, convert to an integer via evaluation at x=2, giving a(9) = 4.

%o (SageMath)

%o P.<x> = GF(2)[]

%o def AD(p):

%o F = list(p.factor())

%o f = [f[0] for f in F for _ in range(f[1])]

%o return SymmetricFunctions(P).e()([len(f)-1,0]).expand(len(f))(f)

%o def more(l):

%o return [x*p for p in l]+[x*p+1 for p in l]

%o L = [x, x+1]

%o L = L + more(L) + more(more(L)) + more(more(more(L))) + more(more(more(more(L))))

%o L.sort()

%o ', '.join(map(str,([0,0]+[AD(p).change_ring(ZZ)(2) for p in L])))

%Y Cf. A003415, A099379, A099380.

%K nonn

%O 0,9

%A _Keith J. Bauer_, Feb 27 2024