×

zbMATH — the first resource for mathematics

Witt vectors and the algebra of necklaces. (English) Zbl 0545.05009
If \(A\) is a ring with identity, then a string \(S\) (over \(A\)) is an infinite column finite matrix with associated (unital) series \[ \prod_{i,j}(1- S_{ij}z^ j)^{-1},\qquad 1\leq i,j<\infty,\quad S=(S_{ij}). \] \(S\) and \(S'\) are Witt equivalent if their associated series are identical. Witt equivalence is characterized algorithmically, resulting in Theorem 3: \(S\) and \(S'\) are Witt equivalent if and only if there is a string \(T\) which is obtained from both by “carrying” (the combinatorial process). Sums and products are defined and shown to be compatible with Witt equivalence via arguments involving the associated unital series.
If \(A\) is an integral domain of characteristic 0, the commutative ring obtained is naturally isomorphic to the necklace ring \(\text{Nr}(A)\), the other (combinatorial) object studied in the first part of this very interesting paper. \(\text{Nr}(A)\) consists of infinite vectors \((a_ i)\), with addition defined componentwise and multiplication by an involution \((a_ i)\cdot(b_ j)=(c_ n)\), \(\sum_{[i,j]=n}(i,j)a_ ib_ j\). A study of several natural operators on \(\text{Nr}(A)\) leads to a sequence of useful and elegant results, including a derivation of the formula for the number of primitive necklaces in \(\alpha\) colors and \(n\) beads, \[ M(\alpha;n)=\frac 1n \sum_{d(n)}\mu(n/d)\alpha^ d \] and several other observations, e.g., \(M(\alpha \beta;n)=\sum_{[i,j]=n}M(\alpha;i)M(\beta;j)\).
A necklace is obtained by placing colored beads around a circle. A necklace which is asymmetric under rotation is primitive.
As is noted by the authors, the context developed in this paper allows them to provide a set-theoretic (bijection) proof of the cyclotomic identity \[ (1-\alpha z)^{-1}=\prod_{j\geq 1}(1-z^ j)^{- M(\alpha,j)} \] which is natural in various senses of the word. As always with these authors, this paper is highly readable in addition to being instructive.

MSC:
05A10 Factorials, binomial coefficients, combinatorial functions
05A15 Exact enumeration problems, generating functions
13F35 Witt vectors and related rings
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bergman, G.M, Ring schemes, () · Zbl 0203.04302
[2] Cartier, Pierre, Groupes formels associés aux anneux De Witt généralisés, C. R. acad. sci. Paris A, 265, 49-52, (1967) · Zbl 0168.27501
[3] Dieudonne, J, Introduction to the theory of formal groups, (1973), Dekker New York · Zbl 0287.14013
[4] Faltin, F; Metropolis, N; Ross, B; Rota, G.-C, The real numbers as a wreath product, Adv. in math., 16, 278-304, (1975) · Zbl 0314.12101
[5] Hazewinkel, M, Formal groups and applications, (1978), Academic Press New York · Zbl 0454.14020
[6] Lang, S, Algebra, (1965), Addison-Wesley Reading, Mass., · Zbl 0193.34701
[7] Lothare, M, Combinatorics on words, ()
[8] \scMetropolis, N., and Rota, G.-C., On the cyclotomic identity, J. Comb. Theory, to appear.
[9] Rota, Gian-Carlo, Baxter algebras and combinatorial identities, II, Bull. amer. math. soc., 75, 330-334, (1969) · Zbl 0319.05008
[10] Rota, Gian-Carlo; Smith, David A, Enumeration under group action, Ann. scuola norm. sup. Pisa, 4, 637-646, (1977) · Zbl 0367.05008
[11] Schur, I, Gesammelte abhandlungen, (1973), Springer-Verlag New York
[12] Viennot, G, Algèbres de Lie libres et monoïdes libres, (1978), Springer-Verlag New York · Zbl 0395.17003
[13] Witt, E, Zyklische Körper und algebren der charakteristik p vom Grad pn, J. reine angew. math., 176, 126-140, (1937) · JFM 62.1112.03
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.