Classical Results on Primitive and Recent Results on Cross-Primitive Sequences

Summary When the kind invitation of Ron Graham and Jaroslav Nešetřil, to write in honour of Paul Erdős about aspects of his work, reached us, our first reaction was to follow it with great pleasure. Our second reaction was not as clear: Which one among the many subjects in mathematics, to which he has made fundamental contributions, should we choose? Finally we just followed the most natural idea to write about an area which just had started to fascinate us: Density Theory for Integer Sequences. More specifically we add here to the classical theory of primitive sequences and their sets of multiples results for cross-primitive sequences, a concept, which we introduce. We consider both, density properties for finite and infinite sequences. In the course of these investigations we naturally come across the main theorems in the classical theory and the predominance of results due to Paul Erdős becomes apparent. Several times he had exactly proved the theorems we wanted to prove! Many of them belong to his earliest contribution to mathematics in his early twenties. Quite luckily our random approach led us to the perhaps most formidable period in Erdős’ work. It reminds us about a statement, which K. Reidemeister [18, ch. 8] made about Carl Friedrich Gauss: “…Aber das Epochale ist doch die geniale Entdeckung des Jünglings: die Zahlentheorie.”