login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer 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). 1
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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.

LINKS

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

FORMULA

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.

EXAMPLE

Table begins:

   0,

   3,     0,

   7,     7,     0,

  15,    35,    15,   0,

  31,  1023,   155,  31,  0,

  63, 18879, 56079, 651, 63, 0,

  ...

MATHEMATICA

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

PROG

(PARI) 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

CROSSREFS

Cf. A022166.

Sequence in context: A201573 A021329 A244809 * A201900 A344387 A019970

Adjacent sequences:  A316551 A316552 A316553 * A316555 A316556 A316557

KEYWORD

nonn,tabl

AUTHOR

Ana Salagean, Jul 06 2018

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 20 21:39 EDT 2022. Contains 353876 sequences. (Running on oeis4.)