Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Entropy

Recent Progresses in Characterising Information Inequalities

Terence Chan

Published Jan 31, 2011• 34 citations
Publisher

Abstract

In this paper, we present a revision on some of the recent progresses made in characterising and understanding information inequalities, which are the fundamental physical laws in communications and compression. We will begin with the introduction of a geometric framework for information inequalities, followed by the first non-Shannon inequality proved by Zhang et al. in 1998 [1]. The discovery of this non-Shannon inequality is a breakthrough in the area and has led to the subsequent discovery of many more non-Shannon inequalities. We will also review the close relations between information inequalities and other research areas such as Kolmogorov complexity, determinantal inequalities, and group-theoretic inequalities. These relations have led to non-traditional techniques in proving information inequalities and at the same time made impacts back onthose related areas by the introduction of information-theoretic tools.

DOI
10.3390/e13020379

Related papers

A new class of non-Shannon-type inequalities for entropies

Konstantin Makarychev, Yury Makarychev, Andrei Romashchenko +1 more

In this paper we prove a countable set of non-Shannon-type linear information inequalities for entropies of discrete random variables, i.e., information inequalities which cannot be reduced to the "basic" inequality I(X : Y |Z) ≥ 0. Our results generalize the inequalities of Z. Zhang and R. Yeung (1998) who found the first examples of non-Shannon-type information inequalities.

Communications in Information and Systems•Jan 1, 2002•133 citations

Classical Shannon Theory

Mark M. Wilde

We cannot overstate the importance of Shannon's contribution to modern science. His introduction of the field of information theory and his solutions to its two main theorems demonstrate that his ideas on communication were far beyond the other prevailing ideas in this domain around 1948. In this chapter, our aim is to discuss Shannon's two main contributions in a descriptive fashion. The goal of this high-level discussion is to build up the intuition for the problem domain of information theory and to understand the main concepts before we delve into the analogous quantum information-theoretic ideas. We avoid going into deep technical detail in this chapter, leaving such details for later chapters where we formally prove both classical and quantum Shannon-theoretic coding theorems. We do use some mathematics from probability theory, namely, the law of large numbers. We will be delving into the technical details of this chapter's material in later chapters (specifically, Chapters 10, 12, and 13). Once you have reached later chapters that develop some more technical details, it might be helpful to turn back to this chapter to get an overall flavor for the motivation of the development. Data Compression We first discuss the problem of data compression. Those who are familiar with the Internet have used several popular data formats such as JPEG, MPEG, ZIP, GIF, etc. All of these file formats have corresponding algorithms for compressing the output of an information source.

Cambridge University Press eBooks•Apr 18, 2013•0 citations

Classical Shannon Theory

Mark M. Wilde

We cannot overstate the importance of Shannon's contribution to modern science. His introduction of the field of information theory and his solutions to its two main theorems demonstrate that his ideas on communication were far beyond the other prevailing ideas in this domain around 1948. In this chapter, our aim is to discuss Shannon's two main contributions in a descriptive fashion. The goal of this high-level discussion is to build up the intuition for the problem domain of information theory and to understand the main concepts before we delve into the analogous quantum information-theoretic ideas. We avoid going into deep technical detail in this chapter, leaving such details for later chapters where we formally prove both classical and quantum Shannontheoretic coding theorems. We do use some mathematics from probability theory (namely, the law of large numbers). We will be delving into the technical details of this chapter's material in later chapters (specifically, Chapters 10, 13, and 14). Once you have reached later chapters that develop some more technical details, it might be helpful to turn back to this chapter to get an overall flavor for the motivation of the development. Data Compression We first discuss the problem of data compression. Those who are familiar with the Internet have used several popular data formats such as JPEG, MPEG, ZIP, GIF, etc. All of these file formats have corresponding algorithms for compressing the output of an information source. A first glance at the compression problem might lead one to believe that it is not possible to compress the output of the information source to an arbitrarily small size, and Shannon proved that this is the case. This result is the content of Shannon's first noiseless coding theorem. An Example of Data Compression We begin with a simple example that illustrates the concept of an information source. We then develop a scheme for coding this source so that it requires fewer bits to represent its output faithfully. Suppose that Alice is a sender and Bob is a receiver. Suppose further that a noiseless bit channel connects Alice to Bob—a noiseless bit channel is one that transmits information perfectly from sender to receiver, e.g., Bob receives “0” if Alice transmits “0” and Bob receives “1” if Alice transmits “1.”

Cambridge University Press eBooks•Nov 2, 2016•0 citations

Information-theoretic security

Imre Csiszár, János Körner

Contemporary techniques of data security are primarily based on computational complexity, typically on the infeasibility of inverting certain functions using currently available mathematical techniques and computing power. Among the various protocols based on such ideas, those approved by the cryptography community appear secure enough, but mathematical and technological progress may render them insecure in the future. Indeed, past experience suggests that this is likely to happen. Information-theoretic secrecy offers provable security even against an adversary with unlimited computing power. This chapter provides a glimpse into the substantial progress that has been made towards clarifying the theoretical possibilities in this direction. Practical applications are reasonably expected within a much shorter time than capacity-achieving coding techniques have followed Shannon's discovery of the noisy channel coding theorem. Two kinds of problems will be addressed: secure transmission over insecure channels and secret key generation taking advantage of public communication. After introducing necessary concepts and tools in Section 17.1, these problems will be treated in Sections 17.2 and 17.3. Let us emphasize that the mathematical models and techniques will be similar to those in previous chapters. These models, however, are now studied from a non-cooperative aspect: a major goal is to keep (at least) one party ignorant of (at least part of) the information exchanged.

Cambridge University Press eBooks•Jun 30, 2011•10 citations

Information Theory Meets Quantum Chemistry: A Review and Perspective

Yilin Zhao, Dongbo Zhao, Chunying Rong +2 more

In this survey, we begin with a concise introduction to information theory within Shannon's framework, focusing on the key concept of Shannon entropy and its related quantities: relative entropy, joint entropy, conditional entropy, and mutual information. We then demonstrate how to apply these information-theoretic tools in quantum chemistry, adopting either classical or quantum formalisms based on the choice of information carrier involved.

Entropy•Jun 16, 2025•15 citations

Information Inequalities for Five Random Variables

László Csirmaz, Elod P. Csirmaz

The entropic region is formed by the collection of the Shannon entropies of all subvectors of finitely many jointly distributed discrete random variables. For four or more variables, the structure of the entropic region is mostly unknown. We utilize a variant of the Maximum Entropy Method to obtain five-variable non-Shannon entropy inequalities, which delimit the five-variable entropy region. This method adds copies of some of the random variables in generations. A significant reduction in computational complexity, achieved through theoretical considerations and by harnessing the inherent symmetries, allowed us to calculate all five-variable non-Shannon inequalities provided by the first nine generations. Based on the results, we define two infinite collections of such inequalities and prove them to be entropy inequalities. We investigate downward-closed subsets of non-negative lattice points that parameterize these collections, and based on this, we develop an algorithm to enumerate all extremal inequalities. The discovered set of entropy inequalities is conjectured to characterize the applied method completely.

arXiv:2512.23316•Computation•Feb 2, 2026•1 citation
In this paper, we present a revision on some of the recent progresses made in characterising and understanding information inequalities, which are the fundamental physical laws in communications and compression. We will begin with the introduction of a geometric framework for information inequalities, followed by the first non-Shannon inequality proved by Zhang et al. in 1998 [1]. The discovery of this non-Shannon inequality is a breakthrough in the area and has led to the subsequent discovery of many more non-Shannon inequalities. We will also review the close relations between information inequalities and other research areas such as Kolmogorov complexity, determinantal inequalities, and group-theoretic inequalities. These relations have led to non-traditional techniques in proving information inequalities and at the same time made impacts back onthose related areas by the introduction of information-theoretic tools.
We cannot overstate the importance of Shannon's contribution to modern science. His introduction of the field of information theory and his solutions to its two main theorems demonstrate that his ideas on communication were far beyond the other prevailing ideas in this domain around 1948. In this chapter, our aim is to discuss Shannon's two main contributions in a descriptive fashion. The goal of this high-level discussion is to build up the intuition for the problem domain of information theory and to understand the main concepts before we delve into the analogous quantum information-theoretic ideas. We avoid going into deep technical detail in this chapter, leaving such details for later chapters where we formally prove both classical and quantum Shannon-theoretic coding theorems. We do use some mathematics from probability theory, namely, the law of large numbers. We will be delving into the technical details of this chapter's material in later chapters (specifically, Chapters 10, 12, and 13). Once you have reached later chapters that develop some more technical details, it might be helpful to turn back to this chapter to get an overall flavor for the motivation of the development. Data Compression We first discuss the problem of data compression. Those who are familiar with the Internet have used several popular data formats such as JPEG, MPEG, ZIP, GIF, etc. All of these file formats have corresponding algorithms for compressing the output of an information source.
We cannot overstate the importance of Shannon's contribution to modern science. His introduction of the field of information theory and his solutions to its two main theorems demonstrate that his ideas on communication were far beyond the other prevailing ideas in this domain around 1948. In this chapter, our aim is to discuss Shannon's two main contributions in a descriptive fashion. The goal of this high-level discussion is to build up the intuition for the problem domain of information theory and to understand the main concepts before we delve into the analogous quantum information-theoretic ideas. We avoid going into deep technical detail in this chapter, leaving such details for later chapters where we formally prove both classical and quantum Shannontheoretic coding theorems. We do use some mathematics from probability theory (namely, the law of large numbers). We will be delving into the technical details of this chapter's material in later chapters (specifically, Chapters 10, 13, and 14). Once you have reached later chapters that develop some more technical details, it might be helpful to turn back to this chapter to get an overall flavor for the motivation of the development. Data Compression We first discuss the problem of data compression. Those who are familiar with the Internet have used several popular data formats such as JPEG, MPEG, ZIP, GIF, etc. All of these file formats have corresponding algorithms for compressing the output of an information source. A first glance at the compression problem might lead one to believe that it is not possible to compress the output of the information source to an arbitrarily small size, and Shannon proved that this is the case. This result is the content of Shannon's first noiseless coding theorem. An Example of Data Compression We begin with a simple example that illustrates the concept of an information source. We then develop a scheme for coding this source so that it requires fewer bits to represent its output faithfully. Suppose that Alice is a sender and Bob is a receiver. Suppose further that a noiseless bit channel connects Alice to Bob—a noiseless bit channel is one that transmits information perfectly from sender to receiver, e.g., Bob receives “0” if Alice transmits “0” and Bob receives “1” if Alice transmits “1.”
Contemporary techniques of data security are primarily based on computational complexity, typically on the infeasibility of inverting certain functions using currently available mathematical techniques and computing power. Among the various protocols based on such ideas, those approved by the cryptography community appear secure enough, but mathematical and technological progress may render them insecure in the future. Indeed, past experience suggests that this is likely to happen. Information-theoretic secrecy offers provable security even against an adversary with unlimited computing power. This chapter provides a glimpse into the substantial progress that has been made towards clarifying the theoretical possibilities in this direction. Practical applications are reasonably expected within a much shorter time than capacity-achieving coding techniques have followed Shannon's discovery of the noisy channel coding theorem. Two kinds of problems will be addressed: secure transmission over insecure channels and secret key generation taking advantage of public communication. After introducing necessary concepts and tools in Section 17.1, these problems will be treated in Sections 17.2 and 17.3. Let us emphasize that the mathematical models and techniques will be similar to those in previous chapters. These models, however, are now studied from a non-cooperative aspect: a major goal is to keep (at least) one party ignorant of (at least part of) the information exchanged.
The entropic region is formed by the collection of the Shannon entropies of all subvectors of finitely many jointly distributed discrete random variables. For four or more variables, the structure of the entropic region is mostly unknown. We utilize a variant of the Maximum Entropy Method to obtain five-variable non-Shannon entropy inequalities, which delimit the five-variable entropy region. This method adds copies of some of the random variables in generations. A significant reduction in computational complexity, achieved through theoretical considerations and by harnessing the inherent symmetries, allowed us to calculate all five-variable non-Shannon inequalities provided by the first nine generations. Based on the results, we define two infinite collections of such inequalities and prove them to be entropy inequalities. We investigate downward-closed subsets of non-negative lattice points that parameterize these collections, and based on this, we develop an algorithm to enumerate all extremal inequalities. The discovered set of entropy inequalities is conjectured to characterize the applied method completely.