PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

The Augustin Capacity and Center
B. Nakiboğlu
pp. 299–342

Abstract—For any channel, the existence of a unique Augustin mean is established for any positive order and probability mass function on the input set. The Augustin mean is shown to be the unique fixed point of an operator defined in terms of the order and the input distribution. The Augustin information is shown to be continuously differentiable in the order. For any channel and convex constraint set with finite Augustin capacity, the existence of a unique Augustin center and the associated van Erven–Harremoës bound are established. The Augustin–Legendre (A-L) information, capacity, center, and radius are introduced, and the latter three are proved to be equal to the corresponding Rényi–Gallager quantities. The equality of the A-L capacity to the A-L radius for arbitrary channels and the existence of a unique A-L center for channels with finite A-L capacity are established. For all interior points of the feasible set of cost constraints, the cost constrained Augustin capacity and center are expressed in terms of the A-L capacity and center. Certain shift-invariant families of probabilities and certain Gaussian channels are analyzed as examples.

On the Cardinality Spectrum and the Number of Latin Bitrades of Order 3
D. S. Krotov and V. N. Potapov
pp. 343–365

Abstract—By a (Latin) unitrade of order $k$, we call a subset of vertices of the Hamming graph $H(n,k)$ that intersects any maximal clique at either $0$ or $2$ vertices. A bitrade is a bipartite unitrade, i.e., a unitrade that can be split into two independent subsets. We study the cardinality spectrum of bitrades in the Hamming graph $H(n,k)$ with $k=3$ (ternary hypercube) and the growth of the number of such bitrades as $n$ grows. In particular, we determine all possible small (up to $2.5\cdot 2^n$) and large (from $14\cdot 3^{n-3}$) cardinalities of bitrades of dimension $n$ and prove that the cardinality of a bitrade takes only values equivalent to $0$ or $2^n$ modulo $3$ (this result can be treated in terms of a ternary Reed–Muller type code). A part of the results are valid for an arbitrary $k$. For $k=3$ and $n\to\infty$ we prove that the number of nonequivalent bitrades is not less than $2^{(2/3-o(1))n}$ and not greater than $2^{\alpha^n}$, $\alpha<2$ (the growth order of the double logarithm of this number remains unknown). Alternatively, the studied set $B_n$ of bitrades of order $3$ can be defined as follows: $B_0$ consists of three rationals $-1,0,1$; $B_n$ consists of ordered triples $(a,b,c)$ of elements from $B_{n-1}$ such that $a+b+c=0$.

On Lower Bounds on the Spectrum of a Binary Code
M. V. Burnashev
pp. 366–375

Abstract—We refine a lower bound on the spectrum of a binary code. We give a simple derivation of the known bound on the undetected error probability of a binary code.

On a Frankl–Wilson Theorem
A. A. Sagdeev
pp. 376–395

Abstract—We derive an analog of the Frankl–Wilson theorem on independence numbers of some distance graphs. The obtained results are applied to the problem of the chromatic number of a space $\mathbb{R}^n$ with a forbidden equilateral triangle and to the problem of chromatic numbers of distance graphs with large girth.

Search for a Moving Element with the Minimum Total Cardinality of Tests
A. V. Lebedev and V. S. Lebedev
pp. 396–400

Abstract—We consider the moving element search problem with the minimum total cardinality of tests. As a search space, we consider the set of integer points of a segment of length $n$. We prove that the total test cardinality of an asymptotically optimal adaptive strategy is $n+2\sqrt{n}$.