Decomposition orders

Bas Luttik

Recall the Fundamental Theorem of Arithmetic (FTA): every positive natural number can be expressed as a product of prime numbers uniquely determined up to the order of the prime numbers. The usual proof of the FTA proceeds via Euclid's division algorithm, which involves, besides multiplication, also addition in its formulation.

In process theory, several analogues of the FTA have been established, which are all of the following form: every process (definable in some process specification language) is a parallel composition of parallel prime processes uniquely determined up to the order of the parallel prime processes. The connection between the FTA and its analogues in process theory can be formalised within the setting of commutative monoids: like multiplication on natural numbers, parallel composition on processes is commutative and associative and it has an identity element.

On the other hand, in process theory there is no natural binary operation that stands to parallel composition in the same way as addition stands to multiplication. Therefore, the proofs of the analogues of the FTA in process theory are essentially different from the usual proof of the FTA itself. Inspired by the proofs in process theory, we propose the notion of decomposition order for commutative monoids. Our main result is that a commutative monoid admits an analogue of the FTA if, and only if, it has a decomposition order.

In my presentation I will not presuppose any knowledge from process theory.

(Joint work with Vincent van Oostrom.)

back to TU/e Combinatorial Theory Seminar announcements