Information theoretic proofs (a survey).

Abstract: Some theorems that have nothing to do with information theory can be proven using an information-theoretic argument (entropy, or Kolmogorov complexity, or counting via compression). For example, why are there infinitely many prime numbers? If there were only M prime numbers, then each integer could be encoded by the list of M exponents in its prime decomposition, so we could specify each n-bit number by only M×O(log n) bits, a contradiction. We will discuss several examples of proofs of that type, including other bounds for the distribution of prime numbers, but not only them.

Computer scienceMathematics

Audience: researchers in the discipline

Seminar on Algorithmic Aspects of Information Theory

Series comments: This online seminar is a follow up of the Dagstuhl Seminar 22301, www.dagstuhl.de/en/program/calendar/semhp/?semnr=22301.