Boolean Functions

[Jon Awbrey]

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o

here you are taking a linear view of the spaces B^k and B^k -> B,
which may be natural in some applications but unnatural in others.

viewing B = {0, 1} as GF(2) singles out the two boolean functions
that correspond to the field addition and field multipication,
which are XOR (or NEQ) and AND in logical terms, but from the
logical point of view all 16 f : B^2 -> B are equal citizens.
and of course <0, ..., 0> is singled out in the linear pov.

jon awbrey

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o

Gordon Royle wrote:
> 
> 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
> --




o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o