Search

A multidimensional nonnegative matrix is called polystochastic if the sum of entries in each line is equal to $1$. The set of all polystochastic matrices of order $n$ and dimension $d$ is a convex polytope $\Omega_n^d$. In the present paper, we compare known bounds on the number of vertices of the polytope $\Omega_n^d$ and prove that the number of vertices of $\Omega_3^d$ is doubly exponential on $d$., Comment: 8 pages, Section 2 is transferred from arXiv:2311.06905

Denote by Q_d the d-dimensional hypercube. Addressing a recent question we estimate the number of ways the vertex set of Q_d can be partitioned into vertex disjoint smaller cubes. Among other results, we prove that the asymptotic order of this function is not much larger than the number of perfect matchings of Q_d. We also describe several new (and old) questions., Comment: Proofs slightly shortened

It is disproved the Tokareva's conjecture that any balanced boolean function of appropriate degree is a derivative of some bent function. This result is based on new upper bounds for the numbers of bent and plateaued functions., Comment: 3 pages

The logarithm of the number of binary n-variable bent functions is asymptotically less than $11(2^n)/32$ as n tends to infinity. Keywords: boolean function, Walsh--Hadamard transform, plateaued function, bent function, upper bound, Comment: 9 pages

A frequency $n$-cube $F^n(q;l_0,...,l_{m-1})$ is an $n$-dimensional $q$-by-...-by-$q$ array, where $q = l_0+...+l_{m-1}$, filled by numbers $0,...,m-1$ with the property that each line contains exactly $l_i$ cells with symbol $i$, $i = 0,...,m-1$ (a line consists of $q$ cells of the array differing in one coordinate). The trivial upper bound on the number of frequency $n$-cubes is $m^{(q-1)^{n}}$. We improve that lower bound for $n>2$, replacing $q-1$ by a smaller value, by constructing a testing set of size $s^{n}$, $s

A coloring of vertices of a graph is called perfect if, for every vertex, the collection of colors of its neighbors depends only on its own color. The correspondent color partition of vertices is called equitable. We note that a number of bounds (Hoffman bound, Cheeger bound, Bierbrauer--Friedman bound and other) is only reached on perfect $2$-colorings. We show that the Expander Mixing Lemma is another example of an inequality that generates a perfect $2$-coloring. We prove a new upper bound for the size of $S\subset V(G)$ with the fixed average internal degree for an amply regular graph $G$. This bound is reached on the set $S$ if and only if $\{S, V(G)\setminus S\}$ is an equitable partition., Comment: 9 pages

An embedding of a code is a mapping that preserves distances between codewords. We prove that any code with code distance $\rho$ and length $d$ can be embedded into an MDS code with the same code distance and length but under a larger alphabet. As a corollary we obtain embeddings of systems of partial mutually orthogonal Latin cubes and $n$-ary quasigroups., Comment: 7 pages

The number of $n$-ary bent functions is less than $2^{3\cdot2^{n-3}(1+o(1))}$ as $n$ is even and $n\rightarrow\infty$. Keywords: Boolean function, bent function, upper bound

We study sequences of linear or affine codes with uniform weight spectrum, i.e., a part of codewords with any fixed weight tends to zero. It is proved that a sequence of linear codes has a uniform weight spectrum if the number of vectors from codes with weight $1$ grows to infinity. We find an example of a sequence of linear codes such that the dimension of the code is the half of the codelength but it has not a uniform weight spectrum. This example generates eigenfunctions of the Fourier transform with minimal support and partial covering sets. Moreover, we generalize some MacWilliams-type identity. Keywords: weight distribution of code, dual code, MacWilliams identity, Fourier transform, partial covering array

A pair of orthogonal latin cubes of order $q$ is equivalent to an MDS code with distance $3$ or to an ${\rm OA}_1(3,5,q)$ orthogonal array. We construct pairs of orthogonal latin cubes for a sequence of previously unknown orders $q_i=16(18i-1)+4$ and $q'_i=16(18i+5)+4$. The minimal new obtained parameters of orthogonal arrays are ${\rm OA}_1(3,5,84)$. Keywords: latin square, latin cube, MOLS, MDS code, block design, Steiner system, orthogonal array, Comment: New pairs of orthogonal latin 3-cubes are available on the website https://ieee-dataport.org/open-access/graeco-latin-cubes

We obtain the following results. For any prime $q$ the minimal Hamming distance between distinct regular $q$-ary bent functions of $2n$ variables is equal to $q^n$. The number of $q$-ary regular bent functions at the distance $q^n$ from the quadratic bent function $Q_n=x_1x_2+\dots+x_{2n-1}x_{2n}$ is equal to $q^n(q^{n-1}+1)\cdots(q+1)(q-1)$ for $q>2$. The Hamming distance between distinct binary $s$-plateaued functions of $n$ variables is not less than $2^{\frac{s+n-2}{2}}$ and the Hamming distance between distinctternary $s$-plateaued functions of $n$ variables is not less than $3^{\frac{s+n-1}{2}}$. These bounds are tight. For $q=3$ we prove an upper bound on nonlinearity of ternary functions in terms of their correlation immunity. Moreover, functions reaching this bound are plateaued. For $q=2$ analogous result are well known but for large $q$ it seems impossible. Constructions and some properties of $q$-ary plateaued functions are discussed., Comment: 14 pages, the results are partialy reported on XV and XVI International Symposia "Problems of Redundancy in Information and Control Systems"

The number of $n$-ary balanced correlation immune (resilient) Boolean functions of order $\frac{n}{2}$ is not less than $n^{2^{(n/2)-2}(1+o(1))}$ as $n\rightarrow\infty$. Keywords: resilient function, correlation immune function, orthogonal array, Comment: 3 pages

We develop a connection between DP-colorings of $k$-uniform hypergraphs of order $n$ and coverings of $n$-dimensional Boolean hypercube by pairs of antipodal $(n-k)$-dimensional faces. Bernshteyn and Kostochka established that the lower bound on edges in a non-2-DP-colorable $k$-uniform hypergraph is equal to $2^{k-1}$ for odd $k$ and $2^{k-1}+1$ for even $k$. They proved that these bounds are tight for $k=3,4$. In this paper, we prove that the bound is achieved for all odd $k\geq 3$., Comment: The previous versions of paper contains a significant error

An algebraic system from a finite set $\Sigma$ of cardinality $k$ and an $n$-ary operation $f$ invertible in each argument is called an $n$-ary quasigroup of order $k$. An autotopy of an $n$-ary quasigroup $(\Sigma,f)$ is a collection $(\theta_0,\theta_1,...,\theta_n)$ of $n+1$ permutations of $\Sigma$ such that $f(\theta_1(x_1),...,\theta_n(x_n))\equiv \theta_0(f(x_1,\ldots,x_n))$. We show that every $n$-ary quasigroup of order $4$ has at least $2^{[n/2]+2}$ and not more than $6\cdot 4^n$ autotopies. We characterize the $n$-ary quasigroups of order $4$ with $2^{(n+3)/2}$, $2\cdot 4^n$, and $6\cdot 4^n$ autotopies., Comment: English: 21 pages; Russian: 22 pages

A $\lambda$-fold $r$-packing (multiple radius-$r$ covering) in a Hamming metric space is a code $C$ such that the radius-$r$ balls centered in $C$ cover each vertex of the space by not more (not less, respectively) than $\lambda$ times. The well-known $r$-error-correcting codes correspond to the case $\lambda=1$, while in general multifold $r$-packing are related with list decodable codes. We (a) propose asymptotic bounds for the maximum size of a $q$-ary $2$-fold $1$-packing as $q$ grows; (b) prove that a $q$-ary distance-$2$ MDS code of length $n$ is an optimal $n$-fold $1$-packing if $q\ge 2n$; (c) derive an upper bound for the size of a binary $\lambda$-fold $1$-packing and a lower bound for the size of a binary multiple radius-$1$ covering (the last bound allows to update the small-parameters table); (d) classify all optimal binary $2$-fold $1$-packings up to length $9$, in particular, establish the maximum size $96$ of a binary $2$-fold $1$-packing of length $9$; (e) prove some properties of $1$-perfect unitrades, which are a special case of $2$-fold $1$-packings. Keywords: Hamming graph, multifold ball packings, two-fold ball packings, list decodable codes, multiple coverings, completely regular codes, linear programming bound, Comment: 17pp. V.3: revised, added: classification of small binary 2-fold 1-packings (Sect. Va), discussion of multifold perfect codes (Sect. Vb), lower bound on the size of multiple coverings (Sect. IVb) V.2: Sections about MDS codes and unitrades added, the proof in Section II rewritten and completed; other revisions

By a (latin) unitrade, we call a set of vertices of the Hamming graph that is intersects with every maximal clique in $0$ or $2$ vertices. A bitrade is a bipartite unitrade, that is, a unitrade splittable into two independent sets. We study the cardinality spectrum of the 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 (up to $2.5\cdot 2^n$) and large (from $14\cdot 3^{n-3}$) cardinatities of bitrades and prove that the cardinality of a bitrade is compartible to $0$ or $2^n$ modulo $3$ (this result has a treatment in terms of a ternary code of Reed--Muller type). A part of the results is valid for any $k$. We prove that the number of nonequivalent bitrades is not less than $2^{(2/3-o(1))n}$ and is not greater than $2^{\alpha^n}$, $\alpha<2$, as $n\to\infty$., Comment: 18 pp. In Russian

This paper initiates the study of shortening universal cycles (u-cycles) and universal words (u-words) for permutations either by using incomparable elements, or by using non-deterministic symbols. The latter approach is similar in nature to the recent relevant studies for the de Bruijn sequences. A particular result we obtain in this paper is that u-words for $n$-permutations exist of lengths $n!+(1-k)(n-1)$ for $k=0,1,\ldots,(n-2)!$.

The minimal Hamming distance between distinct $p$-ary bent functions of $2n$ variables is proved to be $p^n$ for any prime $p$. It is shown that the number of $p$-ary bent functions at the distance $p^n$ from the quadratic bent function is equal to $p^n(p^{n-1}+1)\cdots(p+1)(p-1)$ as $p>2$., Comment: 2 pages

A Steiner quadruple system (briefly $SQS(n)$) is a pair $(X,B)$ where $|X|=n$ and $B$ is a collection of 4-element blocks such that every 3-subset of $X$ is contained in exactly one member of $B$. Hanani \cite{Hanani} proved that the necessary condition $n\ {\rm mod}\ 6= 2\ {\rm or}\ 4$ for the existence of a Steiner quadruple systems of order $n$ is also sufficient. Lenz \cite{Lenz} proved that the logarithm of the number of different $SQS(n)$ is greater than $cn^3$ where $c>0$ is a constant and $n$ is admissible. We prove that the logarithm of the number of different $SQS(n)$ is $\Theta(n^3\ln n)$ as $n\rightarrow\infty$ and $n\ {\rm mod}\ 6= 2\ {\rm or}\ 4$., Comment: 5 pages. arXiv admin note: substantial text overlap with arXiv:1510.06212

We consider the problem of finding a set (partial covering array) $S$ of vertices of the Boolean $n$-cube having cardinality $2^{n-k}$ and intersecting with maximum number of $k$-dimensional faces. We prove that the ratio between the numbers of the $k$-faces containing elements of $S$ to $k$-faces is less than $1-\frac{1+o(1)}{\sqrt{2\pi k}}$ as $n\rightarrow\infty$ for sufficiently large $k$. The solution of the problem in the class of linear codes is found. Connections between this problem, cryptography and an efficiency of quantization are discussed., Comment: 7 pages

It is established that the logarithm of the number of latin $d$-cubes of order $n$ is $\Theta(n^{d}\ln n)$ and the logarithm of the number of pairs of orthogonal latin squares of order $n$ is $\Theta(n^2\ln n)$. Similar estimations are obtained for systems of mutually strong orthogonal latin $d$-cubes. As a consequence, it is constructed a set of Steiner quadruple systems of order $n$ such that the logarithm of its cardinality is $\Theta(n^3\ln n)$ as $n\rightarrow\infty$ and $n\ {\rm mod}\ 6= 2\ {\rm or}\ 4$., Comment: 10 pages

The idea of (combinatorial) Gray codes is to list objects in question in such a way that two successive objects differ in some pre-specified small way. In this paper, we utilize beta-description trees to cyclicly Gray code three classes of cubic planar maps, namely, bicubic planar maps, 3-connected cubic planar maps, and cubic non-separable planar maps.

The logarithm of the maximum number of transversals over all latin squares of order $n$ is greater than $\frac{n}{6}(\ln n+ O(1))$.

A subset $S$ of $k$-ary $n$-dimensional hypercube is called latin bitrade if $|S\cap F|\in\{0,2\} $ for each 1-face $F$. We find all admissible small (less than $2^{n+1}$) cardinalities of latin bitrades. A subset $M$ of $k$-ary $n$-dimensional hypercube is called $t$-fold MDS code if $|M\cap F|=t $ for each 1-face $F$. Symmetric difference of two 1-fold MDS codes is always a latin bitrade. Symmetric difference of two $t$-fold MDS codes may also be a latin bitrade. In this case we say that this latin bitrade embedded into $t$-fold MDS code. The intersection of $t$-fold MDS code and a latin bitrade embedded into it is called a component of the code. We study the questions of embedding of latin bitrades into $t$-fold MDS and admissible cardinalities of the component of $t$-fold MDS. Keywords: MDS code, latin bitrade, component., Comment: in Russian

A coloring of the $q$-ary $n$-dimensional cube (hypercube) is called perfect if, for every $n$-tuple $x$, the collection of the colors of the neighbors of $x$ depends only on the color of $x$. A Boolean-valued function is called correlation-immune of degree $n-m$ if it takes the value 1 the same number of times for each $m$-dimensional face of the hypercube. Let $f=\chi^S$ be a characteristic function of some subset $S$ of hypercube. In the present paper it is proven the inequality $\rho(S)q({\rm cor}(f)+1)\leq \alpha(S)$, where ${\rm cor}(f)$ is the maximum degree of the correlation immunity of $f$, $\alpha(S)$ is the average number of neighbors in the set $S$ for $n$-tuples in the complement of a set $S$, and $\rho(S)=|S|/q^n$ is the density of the set $S$. Moreover, the function $f$ is a perfect coloring if and only if we obtain an equality in the above formula.Also we find new lower bound for the cardinality of components of perfect coloring and 1-perfect code in the case $q>2$. Keywords: hypercube, perfect coloring, perfect code, MDS code, bitrade, equitable partition, orthogonal array., Comment: 6 pages

A coloring of the Boolean $n$-cube is called perfect if, for every vertex $x$, the collection of the colors of the neighbors of $x$ depends only on the color of $x$. A Boolean function is called correlation-immune of degree $n-m$ if it takes the value 1 the same number of times for each $m$-face of the Boolean $n$-cube. In the present paper it is proven that each Boolean function $\chi^S$ ($S\subset E^n$) satisfies the inequality $${\rm nei}(S)+ 2({\rm cor}(S)+1)(1-\rho(S))\leq n,$$ where ${\rm cor}(S)$ is the maximum degree of the correlation immunity of $\chi^S$, ${\rm nei} (S)= \frac{1}{|S|}\sum\limits_{x\in S}|B(x)\cap S|-1$ is the average number of neighbors in the set $S$ for vertices in $S$, and $\rho(S)=|S|/2^n$ is the density of the set $S$. Moreover, the function $\chi^S$ is a perfect coloring if and only if we obtain an equality in the above formula. Keywords: hypercube, perfect coloring, perfect code, correlation-immune function., Comment: 5 pages

A latin hypercuboid of order $N$ is an $N\times...\times N\times k$ array filled with symbols from the set $\{0,...,N-1\} $ in such a way that every symbol occurs at most once in every line. If $k=N$, such an array is a latin hypercube. We prove that any latin hypercuboid of order 4 is completable to a latin hypercube. Keywords: latin hypercube, n-ary quasigroup, Comment: 5 pages

An $H(n,q,w,t)$ design is considered as a collection of $(n-w)$-faces of the hypercube $Q^n_q$ perfectly piercing all $(n-t)$-faces. We define an $A(n,q,w,t)$ design as a collection of $(n-t)$-faces of hypercube $Q^n_q$ perfectly cowering all $(n-w)$-faces. The numbers of H- and A-designs are expressed in terms of multidimensional permanent. We present several constructions of H- and A-design and prove the existence of $H(2^{t+1},s2^t,2^{t+1}-1,2^{t+1}-2)$ designs for every $s,t\geq 1$. Keywords: perfect matching, clique matching, permanent, MDS code, generalized Steiner system, H-design., Comment: 4 pages