Subject: categories: Addendum

From: Peter Freyd <[email-masked]>
Date: Fri, 26 Mar 2004 08:39:01 -0500 (EST)

I wrote:

  [I]n the category  of  N-sets (sets with a distinguished self-map)
  let  A  be the two-element set in which the distinguished self-map
  has a unique fixed point....A^A, the object of self-maps of  A,
  falls apart as a coproduct (disjoint union) of continuously many
  N-sets. Hence if one takes the set of equivalence classes of  A^A,
  where the equivalence relation is the double-negation of equality,
  one obtains a discrete set (it has trivial N-action) whose
  cardinality is the continuum.

It's more complicated. One obtains a disjoint union of "cycles", that
is, objects of the form  Z/nZ  where the distinguished self-map is
addition by  1. For each  n > 0  there are only a finite number of
copies of  Z/nZ. The number of copies of  Z = Z/0Z  is uncountable.

Postscript:

The sequence of numbers of copies of each finite cycle is, of course,
guaranteed to be in Neil Sloan's "On-Line Encyclopedia of Integer
Sequences", but we didn't have that. Instead in 1.925 of Cats &
Alligators we gave a ridiculous -- but both correct and unimprovable
-- formula for that finite number. Preceding it was a sentence that
begins "Bearing in mind that, as far as we know, this is computation
for its own sake". Anyway, you can find the same formula at

      mathworld.wolfram.com/IrreduciblePolynomial.html

under the name  L_q(n)  (with  q = 2).

With the exception of the zero'th value (in our case it's
2^{\Aleph_0}, for Lyndon words it's 1) here's what Sloan has to say:

ID Number: A001037 (Formerly M0116 and N0046)
URL:       http://www.research.att.com/projects/OEIS?Anum=A001037
Sequence:  1,2,1,2,3,6,9,18,30,56,99,186,335,630,1161,2182,4080,7710,
           14532,27594,52377,99858,190557,364722,698870,1342176,
           2580795,4971008,9586395,18512790,35790267,69273666,
           134215680,260300986,505286415,981706806
Name: Degree n irreducible polynomials over GF(2); n-bead necklaces
           with beads of 2 colors when turning over is not allowed and
           with primitive period n; binary Lyndon words of length n.
Comments:  Also dimensions of free Lie algebras - see A059966, which is
           essentially the same sequence.
References E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, NY, 1968, p.
              84.
           R. Church, Tables of irreducible polynomials for the first
              four prime moduli, Annals Math., 36 (1935), 198-209.
           E. N. Gilbert and J. Riordan, Symmetry types of periodic
              sequences, Illinois J. Math., 5 (1961), 657-665.
           M. A. Harrison, On the classification of Boolean functions
              by the general linear and affine groups, J. Soc. Indust.
              Appl. Math. 12 (1964) 285-299.
           M. Lothaire, Combinatorics on Words. Addison-Wesley,
              Reading, MA, 1983, p. 79.
           G. Melancon, Factorizing infinite words using Maple,
              MapleTech journal, vol 4, no. 1, 1997, pp. 34-42, esp.
              p. 36.
           M. R. Nester, (1999). Mathematical investigations of some
              plant interaction designs. PhD Thesis. University of
              Queensland, Brisbane, Australia.
           G. Viennot, Algebres de Lie Libres et Monoides Libres,
              Lecture Notes in Mathematics 691, Springer verlag 1978.