Ana Salagean - cp's OEIS frontend

User: Ana Salagean

Ana Salagean has authored 1 sequences.

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).

0, 3, 0, 7, 7, 0, 15, 35, 15, 0, 31, 1023, 155, 31, 0, 63, 18879, 56079, 651, 63, 0, 127, 2097151, 128373759, 4090543, 2667, 127, 0, 255, 155553791, 8739796397055, 8761037088127, 534190575, 10795, 255, 0, 511, 68719476735, 36818452141739261951, 603282315201970099093503, 36821430371387013247, 137165789295, 43435, 511, 0

Offset: 1

Ana Salagean, Jul 06 2018

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.
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.
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.
We count the functions which have at least one derivative of degree strictly less than d-1.
This is a triangular array, indexed by (n,d), with d=1..n. It is written row by row, starting with n=1.
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.

			Table begins:
   0,
   3,     0,
   7,     7,     0,
  15,    35,    15,   0,
  31,  1023,   155,  31,  0,
  63, 18879, 56079, 651, 63, 0,
  ...

Michael De Vlieger, Table of n, a(n) for n = 1..105 (rows 1 <= n <= 14, flattened).
A. Salagean and M. Mandache-Salagean, Counting and characterising functions with "fast points" for differential attacks, Cryptography and Communications 9 (2017), 217-239.
Ana Sălăgean, Ferruh Özbudak, Counting Boolean functions with faster points, Designs, Codes and Cryptography (2020).

Cf. A022166.

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 *)

qb(n, k, m) = prod(i=0, k-1, (1 - m^(n-i))/(1-m^(i+1)));
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

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).

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.

cp's OEIS Frontend

User: Ana Salagean

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).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula