login
A329822
The minimum weight of a Boolean function of algebraic degree at most n-3 whose support contains n linearly independent elements.
2
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
C. Beierle, A. Biryukov and A. Udovenko, On degree-d zero-sum sets of full rank, Cryptography and Communications, November 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
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
KEYWORD
nonn,easy
AUTHOR
Christof Beierle, Nov 22 2019
STATUS
approved