We study here the ring 2f(n) of Quasi-symmetric functions in the variables x(1), x(2), . . . , x(n). Bergeron and Reutenauer (personal communication) formulated a number of conjectures about this ring; in particular, they conjectured that it is free over the ring Lambda(n) of symmetric functions in x(1),x(2), . . . x(n). We present here an algorithm that recursively constructs a Lambda(n)-module basis for 2f(n) thereby proving one of the Bergeron-Reutenauer conjectures. This result also implies that the quotient of 2f(n) by the ideal generated by the elementary symmetric functions has dimension n!. Surprisingly, to show the validity of our algorithm we were led to a truly remarkable connection between 2f(n) and the harmonics of S-n. (C) 2003 Elsevier Inc. All rights reserved. [References: 10]
展开▼