If your email box does not support HTML letter, please visit below URL to access the full version of this letter in browser.
www.aimspress.com/Release/collection.html

The collection comprises 11 research papers and an editorial paper, which together address core mathematical aspects of information theory, including information measures, entropy and divergence inequalities, zero-error information theory, graph-theoretic and combinatorial methods, and related topics. We warmly invite you to read these papers and follow the latest developments of our journal. We hope they will serve as a valuable resource for your research.

AIMS Mathematics is Open Access and an international monthly publication devoted to publishing peer-reviewed, high quality, research articles, as well as review articles, related to all aspects of the theory and applications of mathematics. To be published in this journal, an original paper must be correct, new, nontrivial and of interest to a substantial number of readers. Every effort is made to ensure a rigorous but quick editorial process and a rapid publication.

Featured articles

Special issue "Mathematical Foundations of Information Theory"

Igal Sason*

This special issue of AIMS Mathematics is devoted to the theme Mathematical Foundations of Information Theory. The objective of the issue is to present recent research that advances the theoretical underpinnings of information theory through rigorous mathematical analysis, while also highlighting its interactions with neighboring areas such as combinatorics, graph theory, statistics, and optimization. The eleven papers collected in this issue reflect the diversity of contemporary foundational research in information theory. Several contributions address long-standing open problems or develop new structural insights into classical objects, while others introduce refined analytical frameworks or provide exact characterizations of carefully formulated models. Taken together, the papers underscore the continuing role of mathematical depth and precision in shaping the development of information theory. The contributions in this special issue are partitioned into three categories.

Advances in the Shannon capacity of graphs

Nitay Lavi, Igal Sason*

We derive exact values and new bounds for the Shannon capacity of two families of graphs: the q-Kneser graphs and the tadpole graphs. We also construct a countably infinite family of connected graphs whose Shannon capacity is not attained by the independence number of any finite strong power. Building on recent work of Schrijver, we establish sufficient conditions under which the Shannon capacity of a polynomial in graphs, formed via disjoint unions and strong products, equals the corresponding polynomial of the individual capacities, thereby reducing the evaluation of such capacities to that of their components. Finally, we prove an inequality relating the Shannon capacities of the strong product of graphs and their disjoint union, which yields alternative proofs of several known bounds as well as new tightness conditions. In addition to contributing to the computation of the Shannon capacity of graphs, this paper is intended to serve as an accessible entry point to those wishing to work in this area.

Amos Lapidoth, Baohua Ni*

A two-to-one memoryless state-dependent multiple-access channel is studied in a setting where helpers that observe the state sequence causally provide rate-limited (lossy) causal descriptions of it to the encoders. It is shown that, when the receiver is cognizant of the channel state, the optimal causal descriptions take the form of scalar symbol-by-symbol quantizers whose descriptions of the current state do not depend on the past states. This holds irrespective of whether the description is provided to both encoders (the "common description" architecture), to one of the encoders (the "one-sided description" architecture), or whether different descriptions are provided to the different encoders (the "general" architecture). In fact, in the common description architecture, it also holds when the encoders can crib. Thus, the prevalent assumption that the receiver is cognizant of the channel state greatly simplifies the design of the state quantizer.

Igal Sason*

This letter addresses an open question concerning a variant of the Lovász ϑ-function, which was introduced by Schrijver and independently by McEliece et al. (1978). The question of whether this variant provides an upper bound on the Shannon capacity of a graph was explicitly stated by Bi and Tang (2019). This letter presents an explicit example of a graph on 32 vertices, which shows that, in contrast to the Lovász ϑ-function, this variant does not necessarily upper bound the Shannon capacity of a graph. The example, previously outlined by the author in a recent paper (2024), is presented here in full detail, making it easy to follow and verify. By resolving this question, the note clarifies a subtle but significant distinction between these two closely related graph invariants.

Output statistics, equivocation, and state masking

Ligong Wang*

Given a discrete memoryless channel and a target distribution on its output alphabet, one wishes to construct a length-n rate-R codebook such that the output distribution—computed over a codeword that is chosen uniformly at random—should be close to the n-fold tensor product of the target distribution. Here "close" means that the relative entropy between the output distribution and said n-fold product should be small. We characterize the smallest achievable relative entropy divided by n as n tends to infinity. We then demonstrate two applications of this result. The first application is an alternative proof of the achievability of the rate-equivocation region of the wiretap channel. The second application is a new capacity result for communication subject to state masking in the scenario where the decoder has access to channel-state information.

Empirical coordination of separable quantum correlations

Husein Natur, Uzi Pereg*

We introduce the notion of empirical coordination for quantum correlations. Quantum mechanics enables the calculation of probabilities for experimental outcomes, emphasizing statistical averages rather than detailed descriptions of individual events. Empirical coordination is thus a natural framework for quantum systems. Focusing on the cascade network, the optimal coordination rates are established, indicating the minimal resources required to simulate, on average, a quantum state. As we consider a network with classical communication links, superposition cannot be maintained, hence the quantum correlations are separable (i.e., a convex combination of product states). This precludes entanglement. Providing the users with shared randomness, before communication begins, does not affect the optimal rates for empirical coordination. We begin with a rate characterization for a basic two-node network, and then generalize to a cascade network. The special case of a network with an isolated node is considered as well. The results can be further generalized to other networks as our analysis includes a generic achievability scheme. The optimal rate formula involves optimization over a collection of state extensions. This is a unique feature of the quantum setting, as the classical parallel does not include optimization. As demonstrated through examples, the performance depends heavily on the choice of decomposition. We further discuss the consequences of our results for quantum cooperative games.

Testing for correlation in Gaussian databases via local decision making

Ran Tamir*

We propose a computationally efficient statistical test for detecting correlation between two Gaussian databases. The problem is formulated as a hypothesis test: under the null hypothesis, the databases are independent; under the alternative hypothesis, they are correlated but subject to an unknown row permutation. We derive bounds on both type Ⅰ and type Ⅱ error probabilities and demonstrate that the proposed test outperforms a recently introduced method across a broad range of parameter settings. The test statistic is based on a sum of dependent indicator random variables. To effectively bound the type Ⅰ error probability, we introduce a novel graph-theoretic technique for bounding the k-th moments of such statistics.

On H-intersecting graph families and counting of homomorphisms

Igal Sason*

This work derives an upper bound on the maximum cardinality of a family of graphs on a fixed number of vertices, in which the intersection of every two graphs in that family contains a subgraph that is isomorphic to a specified graph H. Such families are referred to as H-intersecting graph families. The bound is derived using the combinatorial version of Shearer's lemma, and it forms a nontrivial extension of the bound derived by Chung, Graham, Frankl, and Shearer (1986), where H is specialized to a triangle. The derived bound is expressed in terms of the chromatic number of H, while a relaxed version, formulated using the Lovász ϑ-function of the complement o H, offers reduced computational complexity. Additionally, a probabilistic version of Shearer's lemma, combined with properties of Shannon entropy, are employed to establish bounds related to the enumeration of graph homomorphisms, providing further insights into the interplay between combinatorial structures and information-theoretic principles.

Correction: Relative information spectra with applications to statistical inference

Sergio Verdú*

Relative information spectra with applications to statistical inference

Sergio Verdú*

For any pair of probability measures defined on a common space, their relative information spectra——specifically, the distribution functions of the loglikelihood ratio under either probability measure——fully encapsulate all that is relevant for distinguishing them. This paper explores the properties of the relative information spectra and their connections to various measures of discrepancy including total variation distance, relative entropy, Rényi divergence, and general f-divergences. A simple definition of sufficient statistics, termed I-sufficiency, is introduced and shown to coincide with longstanding notions under the assumptions that the data model is dominated and the observation space is standard. Additionally, a new measure of discrepancy between probability measures, the NP-divergence, is proposed and shown to determine the area of the error probability pairs achieved by the Neyman-Pearson binary hypothesis tests. For independent identically distributed data models, that area is shown to approach 1 at a rate governed by the Bhattacharyya distance.

Observations on graph invariants with the Lovász ϑ-function

Igal Sason*

This paper delves into three research directions, leveraging the Lovász ϑ-function of a graph. First, it focuses on the Shannon capacity of graphs, providing new results that determine the capacity for two infinite subclasses of strongly regular graphs, and extending prior results. The second part explores cospectral and nonisomorphic graphs, drawing on a work by Berman and Hamud (2024), and it derives related properties of two types of joins of graphs. For every even integer such that n≥14, it is constructively proven that there exist connected, irregular, cospectral, and nonisomorphic graphs on n vertices, being jointly cospectral with respect to their adjacency, Laplacian, signless Laplacian, and normalized Laplacian matrices, while also sharing identical independence, clique, and chromatic numbers, but being distinguished by their Lovász ϑ-functions. The third part focuses on establishing bounds on graph invariants, particularly emphasizing strongly regular graphs and triangle-free graphs, and compares the tightness of these bounds to existing ones. The paper derives spectral upper and lower bounds on the vector and strict vector chromatic numbers of regular graphs, providing sufficient conditions for the attainability of these bounds. Exact closed-form expressions for the vector and strict vector chromatic numbers are derived for all strongly regular graphs and for all graphs that are vertex- and edge-transitive, demonstrating that these two types of chromatic numbers coincide for every such graph. This work resolves a query regarding the variant of the ϑ-function by Schrijver and the identical function by McEliece et al. (1978). It shows, by a counterexample, that the ϑ-function variant by Schrijver does not possess the property of the Lovász ϑ-function of forming an upper bound on the Shannon capacity of a graph. This research paper also serves as a tutorial of mutual interest in zero-error information theory and algebraic graph theory.

Claude Carlet*

Determining the weight distribution of all Reed-Muller codes is a huge and exciting problem that has been around since the sixties. Some progress has been made very recently, but we are still far from a solution. In this paper, we addressed the subproblem of determining as many codeword weights as possible in Reed-Muller codes of any lengths and any orders, which is decisive for determining their weight spectra (i.e., the lists of all possible weights in these codes). New approaches seem necessary for both the main problem and the subproblem. We first studied the difficulties and the limits of the approach, which consisted of using the usual primary and secondary constructions of Boolean functions for the purpose of determining as many weights as possible in Reed-Muller codes. We then introduced a way, different from the usual constructions, to generate Boolean functions in n variables having an algebraic degree bounded from above, without any restriction on n, and whose Hamming weights can be determined. This provided weights in Reed-Muller codes of any lengths 2ⁿ and any orders, allowing us to reach potentially new values in the weight spectra of Reed-Muller codes (as we illustrate with all Reed-Muller codes of lengths up to 2²¹), with the related codewords being given with their supports and their algebraic normal forms being mathematically derived.

A note on equivalent conditions for majorization

Roberto Bruno, Ugo Vaccaro*

In this paper, we introduced novel characterizations of the classical concept of majorization in terms of upper triangular (resp., lower triangular) row-stochastic matrices, and in terms of sequences of linear transforms on vectors. We use our new characterizations of majorization to derive an improved entropy inequality.

Special issue: “Mathematical Foundations of Information Theory”
Guest Editor:
Prof. Igal Sason
Andrew & Erna Viterbi Faculty of Electrical and Computer Engineering, Technion—Israel Institute of Technology, Haifa 3200003, Israel
Faculty of Mathematics, Technion—Israel Institute of Technology, Haifa 3200003, Israel
Email: eeigal@technion.ac.il
Special issue website: https://www.aimspress.com/math/article/6539/special-articles
Journal Home
https://www.aimspress.com/journal/Math
Email: Math@aimspress.org