Boolean Functions

[Gordon Royle]

Regarding boolean functions, my confusion was partly caused by the fact
that the thing being counted seems - to me - to not be the natural
thing to count under some of the groups being used.

More particularly, let's consider the usual boolean function as a map
from 

	GF(2)^n -> GF(2)

where GF(2) = {0,1} = finite field of order 2.


Then the inverse image of "1" is a subset of GF(2)^n and so we can really
view a boolean function as simply picking out a subset of GF(2)^n.

Now, in A053874, we consider equivalence classes under the group GL(n,2) -
the set of all invertible nxn matrices over GF(2). 

Under this group, the vector (0,0,...,0) is fixed, but the group is
transitive on the other vectors.  So its "natural" action is really on the 
subsets of non-zero vectors of GF(2)^n  - that is, subsets of the
projective space PG(n-1,2). If we really *do* want to consider the
zero vector, then we can simply  include/omit it arbitrarily into any
of the subsets of non-zero vectors.


For example, under GL(3,2) we get the following numbers of equivalence 
classes of subsets of non-zero vectors.

	1 of size 0
	1 of size 1
	1 of size 2
	2 of size 3
	2 of size 4
	1 of size 5
	1 of size 6
	1 of size 7

Now, we can arbitrarily add the zero vector to all of these, which would
increase their size by one, yielding (in total)
	
	1 	of size 0
	1 + 1	of size 1
	1 + 1 	of size 2
	2 + 1 	of size 3
	2 + 2 	of size 4
	1 + 2 	of size 5
	1 + 1 	of size 6
	1 + 1 	of size 7
	    1 	of size 8

which is the row [1,2,2,3,4,3,2,2,1] from A053874.


For me, the former sequence (zero vector omitted) is the more natural
since it counts

	- number of k-subsets of points in projective space,
	- number of k-element simple loopless binary matroids of rank <= n,
and for n<6,
	- number of Cayley graphs of Z_2^n with degree k


-- 
Dr. Gordon F Royle, http://www.csse.uwa.edu.au/~gordon, gordon at csse.uwa.edu.au
--