Comments from Augustine Munagi (munagi(AT)maths.wits.ac.za), Jan 30 2007 A collection of nonempty sets S_1,S_2,... is called a system of complementing subsets for a set X of nonnegative integers if every x in X can be represented uniquely as a sum x = s_1 + s_2 + ... with s_i in S_i for all i. We also write X = S_1 "+" S_2 "+" .... (where "+" stands for the direct sum symbol). If there is a positive integer k such that X = S_1"+"S_2"+" ... "+"S_k, then {S_1, S_2,... , S_k} is called a complementing k-tuple for X. Notation: CS(X) = set of systems of complementing subsets of X. CS(k,X) = set of complementing k-tuples for X. The problem is to count the elements of CS(N_n), where N_n = {0,1,2,... ,n-1}. This is a fundamental partitioning problem. It can be viewed as a form of set partitions in which the rule of combination is direct sum rather than union. Perhaps most of the mathematicians mentioned below would rather view this as the fundamental number-base or radix representaion problem. In my paper [Mu], I give a full characterization of the set CS(k, X) for any k (and hence CS(N_n)), as well as explicit formulas for the cardinalities of CS(k, N_n) and CS(N_n), thus settling a long-standing open question. In what follows, I extend a portion of the beautiful survey work initiated by Tijdeman [T] (from which I learned of the problem) as it relates to CS(N_n) only. In a fundamental paper [B] de Bruijn characterizes CS(N), N = {0,1,2,... }, even though he was inspired by a class of finite number base representations which he calls "British Number Systems". C. T. Long gives a precise statement of the finite case, namely characterize and enumerate CS(k, N_n) for any positive integer k, or the whole system CS(N_n). He used an algebraic proof to show that |CS(2, N_n)| = f(n), the number of ordered factorization of n, where his count includes {{0}, N_n}. L. Carlitz and L. Moser [CM] considered the problem under the guise of F-factorizations of (1-x^n)/(1-x), and obtained the enumerative formula for Prime Complementing Systems of Subsets of N_n, namely (x_1+x_2+...+x_r) /(x_1!x_2!...x_r!), where n = p1^x1.p2^x2.....pr^xr is the canonical factorization of n as a product of primes. (This is the number of elements of CS(N_n) in which every subset has prime cardinality, or the number of oredered factorizations of n into primes). They then went on to prove an assertion equivalent to |CS(2,n)| = f(n), in which the count includes {{0}, N_n}. Golomb [G] discusses the base n representation, but goes on to characterize the set CS(N_n) in the case n = p^m (p a prime), without giving any counting result. Kobel [K] gives what he claims to be a solution to a problem posed by Golomb. In a 4-page article [K], he dwells extensively on factorizations of cyclotomic polynomials to provide a characterization of the case n = b^m-1, thus generalizing Golomb's puzzle which seeks the description of all the representations defined as follows: "Let b>1 be an integer and let U and V be sets, each of b nonnegative integers, such that every nonnegative integer up to b^2-1 can be uniquely written in the form u+v with u in U and v in V." Lagarias and Wang [LW] tackle the generalization of the radix representation problem originally posed by Knuth (Art of Comp. Prog. Vol. II), and notes that Odlyzko [O] had earlier proved that the minimal collections of feasible sets for base b radix representations are precisely the members of CS(N_b). Odlyzko had used techniques that include the factorization methods of Carltz and Moser [CM] to give existential and not enumerative proof. The foregoing is only a few of the mathematicians who have grappled with this fundamental direct-sum decomposition problem, directly or indirectly. A more complete list would include names like A. D. Sands, G. Hajos. C. B. Swenson, and L. Redei, besides D. E.Knuth and G. E. Andrews, etc. The massive literature on the factorization theory of finite abelian groups is due partly to the difficulty in characterizing the set CS(N_n). We may compare A104725 with either A074206 (ordered factorizations) and A002033 (perfect partitions), which is actually a restricted case of it. REFERENCES [B] N. G. de Bruijn, On Number Systems, Nieuw Archief voor Wiskunde (3), 4, (1956), 15-17. [CM] L. Carlitz and L. Moser, On Some Special Factorizations of (1-x^n)/(1-x), Canad. Math. Bull., No. 4, 9 (1966) 421-426. [G] S. W. Golomb, Some Decompositions of the Integers from 0 to p^n-1, The American Mathematical Monthly, February, 1972, 154-157. [K] D. R. Kobel, Cyclotomic polynomials and base b representations of integers. Solution to Solomon Golomb's puzzle "Two-digit base b representations," IEEE Information Theory Society Newsletter, March 1997. [LW] J. C. Lagarias and Y. Wang, Nonnegative Radix Representations for the Orthant (1996), Transactions of the American Mathematical Society, Vol. 348, No. 1. (Jan., 1996), pp. 99-117. [L] C. T. Long, C. T., Addition Theorems for sets of Integers, Pacific J. Math. 23 (1967) 107-112. [Ma] MathSciNet, MR2143753 (2006c:11008). [Mu] A. O. Munagi, k-Complementing Subsets of Nonnegative Integers, Int. J. Math. Math. Sci. 2005 (2005), no. 2, 215-224. [O] A. M. Odlyzko , Nonnegative digit sets in positional number systems, Proc. London Math. Soc. (3), 37 (1978), pp. 213-229 [T] R. Tijdeman, Decomposition of the integers as a direct sum of two subsets, Number Theory (Paris, 1992-1993), London Math. Soc. Lecture Note Ser., vol. 215, Cambridge Univ. Press, Cambridge, 1995, pp. 261 276. Augustine O. Munagi The John Knopfmacher Centre for Applicable Analysis and Number Theory School of Mathematics University of the Witwatersrand Johannesburg 2050 South Africa