A329822 The minimum weight of a Boolean function of algebraic degree at most n-3 whose support contains n linearly independent elements.

8, 8, 12, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 106, 108, 110, 112, 114, 116, 118, 120, 122, 124, 126, 128

Offset

3,1

Comments

Equivalently, a(n) is the minimum number for which there exists a subset S of GF(2)^n with a(n) elements which spans GF(2)^n as a vector space and Sum_{s in S} f(s) = 0 for all n-bit Boolean functions of algebraic degree at most 2.

Links

Colin Barker, Table of n, a(n) for n = 3..1000

C. Beierle, A. Biryukov and A. Udovenko, On degree-d zero-sum sets of full rank, Cryptography and Communications, November 2019.

Index entries for linear recurrences with constant coefficients, signature (2,-1).

Formula

For n = 4 and n > 5, a(n) = 2n. As exceptions, a(3) = 8, a(5) = 12. Proven in Beierle, Biryukov, Udovenko, 2019.

From Colin Barker, Nov 22 2019: (Start)

G.f.: 2*x^3*(4 - 4*x + 2*x^2 - 2*x^3 + x^4) / (1 - x)^2.

a(n) = 2*a(n-1) - a(n-2) for n>7.

(End)

E.g.f.: 2*(-1 + exp(x))*x -2*x^2 + x^3/3 + x^5/60. - Stefano Spezia, Nov 22 2019

Mathematica

Drop[#, 3] &@ CoefficientList[Series[2 x^3*(4 - 4 x + 2 x^2 - 2 x^3 + x^4)/(1 - x)^2, {x, 0, 64}], x] (* Michael De Vlieger, Nov 22 2019 *)

Prog

(PARI) Vec(2*x^3*(4 - 4*x + 2*x^2 - 2*x^3 + x^4) / (1 - x)^2 + O(x^60)) \\ Colin Barker, Nov 22 2019

Crossrefs

A052928(n+2) gives the minimum weight of a Boolean function of algebraic degree at most n-2 whose support contains n linearly independent elements (n >= 2).

Sequence in context: A213746 A219236 A259532 * A226835 A363326 A343526

Adjacent sequences: A329819 A329820 A329821 * A329823 A329824 A329825

Keyword

nonn,easy

Author

Christof Beierle, Nov 22 2019

Status

approved