[math-fun] a hard sequence worthy of attention
There was some discussion on this list a while back about sequences that would make good projects. Here is an old one where nothing has been done for many years: %I A001289 %S A001289 1,2,3,8,48,150357 %N A001289 Number of equivalence classes of Boolean functions modulo linear functions. %C A001289 Number of equivalence classes of maps from GF(2)^n to GF(2), where maps f and g are equivalent iff there exists an invertible n X n binary matrix M, two n-dimensional binary vectors a and b, and a binary scalar c such that g(x) = f(Mx+a) + b.x + c. %D A001289 Berlekamp, Elwyn R. and Welch, Lloyd R., Weight distributions of the cosets of the (32,6) Reed-Muller code, IEEE Trans. Information Theory, IT-18 (1972), 203-207. %D A001289 R. J. Lechner, Harmonic Analysis of Switching Functions, in A. Mukhopadhyay, ed., Recent Developments in Switching Theory, Acad. Press, 1971, pp. 121-254, esp. p. 186. %D A001289 F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier-North Holland, 1977, p. 431. %D A001289 I. Strazdins, Universal affine classification of Boolean functions, Acta Applic. Math. 46 (1997), 147-167. %H A001289 <a href="http://www.research.att.com/~njas/sequences/Sindx_Bo.html#Boolean">Index entries for sequences related to Boolean functions</a> %Y A001289 Adjacent sequences: A001286 A001287 A001288 this_sequence A001290 A001291 A001292 %Y A001289 Sequence in context: A013208 A094370 A066084 this_sequence A103045 A041979 A001686 %K A001289 nonn,hard %O A001289 1,2 %A A001289 njas It is important in the study of Reed-Muller codes. NJAS
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o just to check, do you mean the 2^n boolean functions that are linear over B = GF(2), i.e., viewing B^n as a finite dimensional vector space, their number is equal to |B^n|? ja N. J. A. Sloane wrote:
There was some discussion on this list a while back about sequences that would make good projects.
Here is an old one where nothing has been done for many years:
%I A001289 %S A001289 1,2,3,8,48,150357
<...>
It is important in the study of Reed-Muller codes.
NJAS
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o inquiry e-lab: http://stderr.org/pipermail/inquiry/ o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
J.A. said: just to check, do you mean the 2^n boolean functions that are linear over B = GF(2), i.e., viewing B^n as a finite dimensional vector space, their number is equal to |B^n|? Me: I am talking about the 2^2^n Boolean functions of n variables, counting them mod addition of linear functions together with all the usual symmetries. NJAS
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o please be gentle, as i'm not really in my math mode today ... B = GF(2) = {0, 1} there are 2^(2^n) functions f : B^n -> B. check. but only 2^n linear functions L = {linear v : B^n -> B}, if those are the ones that you mean. so f = g mod L if f - g is in L? but i don't know what you are counting as usual symmetries here. ja N. J. A. Sloane wrote:
J.A. said: just to check, do you mean the 2^n boolean functions that are linear over B = GF(2), i.e., viewing B^n as a finite dimensional vector space, their number is equal to |B^n|?
Me: I am talking about the 2^2^n Boolean functions of n variables, counting them mod addition of linear functions together with all the usual symmetries. NJAS
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o inquiry e-lab: http://stderr.org/pipermail/inquiry/ o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
participants (2)
-
Jon Awbrey -
N. J. A. Sloane