cp's OEIS Frontend

A316554 Triangle read by rows: number of Boolean functions in n variables, of algebraic degree d, with the property that at least one of their discrete derivatives has degree strictly smaller than d-1 (d-1 is maximum possible degree).

%I A316554 #34 Jun 17 2020 02:15:07
%S A316554 0,3,0,7,7,0,15,35,15,0,31,1023,155,31,0,63,18879,56079,651,63,0,127,
%T A316554 2097151,128373759,4090543,2667,127,0,255,155553791,8739796397055,
%U A316554 8761037088127,534190575,10795,255,0,511,68719476735,36818452141739261951,603282315201970099093503,36821430371387013247,137165789295,43435,511,0
%N A316554 Triangle read by rows: number of Boolean functions in n variables, of algebraic degree d, with the property that at least one of their discrete derivatives has degree strictly smaller than d-1 (d-1 is maximum possible degree).
%C A316554 Boolean functions in n variables (n bits input, one bit output) are viewed in their algebraic normal form (ANF), i.e., as polynomial functions over F_2 (the finite field of integers modulo 2), of degree at most one in each variable.
%C A316554 The functions are counted up to equivalence: two functions are defined as equivalent if they both have the same degree d and their difference is a polynomial function of degree d-1.
%C A316554 The discrete derivative of f in direction (a_1,...,a_n) is defined as f(x_1+a_1,...,x_n+a_n) - f(x_1,...,x_n); if f has degree d, its derivatives have degree d-1 or less.
%C A316554 We count the functions which have at least one derivative of degree strictly less than d-1.
%C A316554 This is a triangular array, indexed by (n,d), with d=1..n. It is written row by row, starting with n=1.
%C A316554 Note that in the Formula section we denoted by qbinomial(n,k,q) the Gaussian binomial coefficients, or q-binomial coefficients; we use the values for q=2, which are sequence A022166. Both formulae were proven in the reference.
%H A316554 Michael De Vlieger, <a href="/A316554/b316554.txt">Table of n, a(n) for n = 1..105</a> (rows 1 <= n <= 14, flattened).
%H A316554 A. Salagean and M. Mandache-Salagean, <a href="https://doi.org/10.1007/s12095-015-0166-1">Counting and characterising functions with "fast points" for differential attacks</a>, Cryptography and Communications 9 (2017), 217-239.
%H A316554 Ana Sălăgean, Ferruh Özbudak, <a href="https://doi.org/10.1007/s10623-020-00738-7">Counting Boolean functions with faster points</a>, Designs, Codes and Cryptography (2020).
%F A316554 T(n,d) = Sum_{i=1..n-d} (-1)^(i-1) 2^(i(i-1)/2) qbinomial(n,i,2) (2^binomial(n-i,d)-1).
%F A316554 Recurrence relation on n, for each fixed d: T(n,d) = Sum_{i=1..(n-d)} qbinomial(n,i,2) (2^binomial(n-i,d) - 1 - T(n-i,d)); T(d,d) = 0.
%e A316554 Table begins:
%e A316554    0,
%e A316554    3,     0,
%e A316554    7,     7,     0,
%e A316554   15,    35,    15,   0,
%e A316554   31,  1023,   155,  31,  0,
%e A316554   63, 18879, 56079, 651, 63, 0,
%e A316554   ...
%t A316554 Block[{f}, f[n_, k_, m_] := Product[(1 - m^(n - i))/(1 - m^(i + 1)), {i, 0, k - 1}]; Table[Sum[(-1)^(i - 1)*2^(i (i - 1)/2)*f[n, i, 2] (2^Binomial[n - i, k] - 1), {i, n - k}], {n, 9}, {k, n}]] // Flatten (* _Michael De Vlieger_, Jun 16 2020 *)
%o A316554 (PARI) qb(n, k, m) = prod(i=0, k-1, (1 - m^(n-i))/(1-m^(i+1)));
%o A316554 T(n, k) = sum(i=1, n-k, (-1)^(i-1)*2^(i*(i-1)/2)*qb(n,i,2)*(2^binomial(n-i,k)-1)); \\ _Michel Marcus_, Jul 22 2018
%Y A316554 Cf. A022166.
%K A316554 nonn,tabl
%O A316554 1,2
%A A316554 _Ana Salagean_, Jul 06 2018