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

Author

Christof Beierle, Nov 22 2019

Keywords

• nonn
• easy

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

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

Programs

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

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

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