Let $C\subseteq\F_2^m$ be a binary linear code and let $[m]=L\sqcup R$ be a bipartition of its coordinates. The \emph{conditional decoding matrix} of $C$ at this cut is the matrix $W$ indexed by $\F_2^{L}\times\F_2^{R}$ whose entry $W(x_L,x_R)$ is the coset-leader weight $d\bigl((x_L,x_R),C\bigr)$, the minimum Hamming distance from the word $(x_L,x_R)$ to the code. We prove that the min-plus factorization rank (Barvinok rank) of $W$, and likewise its tropical rank, equal $2^{s}$ exactly, where $s=\dim C-\dim C_L-\dim C_R$ is the classical state complexity of the minimal trellis of $C$ at the cut. The upper bound is a two-party reading of Viterbi decoding on the minimal trellis; the contribution is the matching lower bound, which holds against arbitrary min-plus factorizations rather than only sequential trellis realizations, and is obtained from an explicit $2^{s}\times 2^{s}$ tropically nonsingular submatrix built from a transversal of codewords. Specializing $C$ to the cut space of a graph identifies $W$ with the conditional ground-state energy of Ising signings (the frustration index), and yields natural graph families whose conditional matrices have min-plus rank exponential in the number of vertices; for these families we also record the contrasting local statement that all bounded-radius views of a signing are switching-trivial, so the exponential rank is carried entirely by non-local structure. We note explicitly that this rank measures representational incompressibility, not computational hardness: planar families attain the same exponential rank while their ground states are computable in polynomial time.
Let $C \le \mathbb{F}_q^n$ be a uniformly random $\mathbb{F}_q$-linear code of rate $1 - h_q(\rho) - \varepsilon$, and let $L^*(C,\rho)$ be the least $L$ such that every Hamming ball of relative radius $\rho$ contains at most $L$ codewords of $C$. That $L^* = \Theta_{q,\rho}(1/\varepsilon)$ has been known since work of Guruswami, H{\aa}stad and Kopparty and of Guruswami and Narayanan. Guruswami, Li, Mosheiff, Resch, Silas and Wootters proved that the constant in front of $1/\varepsilon$ is at least $h_q(\rho)$ for all $q$, along with an upper bound special to $q = 2$ which narrowed $L^*$ to within three consecutive integers in that case. But for $q \ge 3$ no upper bound with the correct constant was known. We determine $L^*$ for every prime power $q$. Let $\zeta := h_q(\rho)/\varepsilon$. For every sufficiently small $\varepsilon$, with probability $1-o(1)$ over the choice of $C$, $$L^*(C,\rho) = \lceil \zeta \rceil,$$ unless the fractional part of $\zeta$ is at most $q^{-\Omega_{q,\rho}(\zeta)}$, in which case $L^*(C,\rho)$ is $\lfloor \zeta \rfloor$ or $\lfloor \zeta \rfloor + 1$. By the threshold characterization of random linear codes due to Mosheiff, Resch, Ron-Zewi, Silas and Wootters, both bounds reduce to a two-sided estimate of a single quantity $V(q,L,\rho)$, where $1-V(q,L,\rho)$ is the threshold rate for $(\rho,L)$-list-decodability. We prove for all large $L$: $$h_q(\rho)(1 + 1/L) - q^{-\Omega_{q,\rho}(L)} \le V(q,L,\rho) \le h_q(\rho)(1 + 1/L).$$ The upper bound rests on a new entropy inequality for sparse random vectors under pairwise non-proportional linear constraints, proved with the Erd\H{o}s-Rado sunflower lemma. The lower bound is an exact analysis of the distribution introduced by Guruswami, Li, Mosheiff, Resch, Silas and Wootters.
Let $A:\mathbb{F}_2^n\to\mathbb{F}_2^m$ be a binary linear map with fixed coordinate bases, let $C_A=\ker A$, and let $\lambda_A(y)$ be the minimum Hamming weight of a preimage of the syndrome $y$. We define $\operatorname{Shat}_{q,s}(A)$ as the least common check support of a $q$-dimensional syndrome subspace whose every nonzero element has coset-leader weight at least $s$. It therefore distinguishes release of $q$ independent syndromes from release of a subspace with no easy linear combination. Deleting check coordinates $F$ releases $\ker A_{\bar{F}}/\ker A$, canonically isomorphic to $(\operatorname{im} A)[F]$. Finiteness implies $R_q(C_A)\ge \mathsf{N}_2(q,s)$, where $\mathsf{N}_2(q,s)$ is the shortest length of a binary code of dimension $q$ and distance at least $s$; profile-Griesmer bounds independently control common check support. The hierarchy is coordinate-relabeling invariant but can change under a change of check basis. For the pair-repetition code $C_n=\{(x,x):x\in\mathbb{F}_2^n\}$, the standard realization $H_0=[I_n\ I_n]$ has $\operatorname{Shat}_{q,s}(H_0)=\mathsf{N}_2(q,s)$ whenever feasible. For every $q\ge 1$ and $s\ge 2$, with $n=\mathsf{N}_2(q,s)$, a row-equivalent realization of the same code has value $q$. For a simplicial coboundary map $A=\delta_k$, check erasure is top-face erasure and the released quotient is emergent cohomology. At $s=1$ the hierarchy reduces to generalized Hamming weights and is Tutte-determined; for $s\ge 2$, even identical labeled cut codes can have different values.
A subspace of $\mathbb{F}_q^n$ is called cyclically covering if the union of $\sigma^i(U)$ can cover the whole space $\mathbb{F}_q^n$, where $\sigma$ is the cyclic shift, $0 \leqslant i \leqslant n-1$. Let $h_q(n)$ be the largest possible co-dimension of a cyclically covering subspace of $\mathbb{F}_q^n$. We show that $h_2(2p) = 2$ for every prime $p$ such that $2$ is a primitive root modulo $p$. By constacyclic codes, we show that $h_q((q-1)n) = 0$ when $h_q(n) = 0$ and $\gcd(n,q-1) = 1$. We also derive a lower bound on $h_q(n)$ by the concept of support weight distribution, which is important in coding theory. Finally, using irreducible cyclic codes, we present several families of $n$ such that $h_q(n) = 0$.
Let $q=p^k$, where $p$ is prime, and let $M$ be a finite matroid representable over ${\Bbb{F}}_q$. Write $\chi_M(t)$ for its characteristic polynomial and $\mbox{decop}(M)$ for the least number of independent sets needed to cover its ground set. We prove that $\chi_M(q)>0$ whenever $k\ge\mbox{decop}(M)$. Geometrically, the central hyperplanes determined by any representation of $M$ fail to cover the dual of the ambient vector space. The proof rests on the Frobenius-power ideals $(X_1^{p^s},\ldots,X_n^{p^s})$, $s\ge1$. Each is preserved by every linear change of coordinates, while nonmembership records the existence of a monomial whose exponent in every variable is bounded. This permits successive normalizations of several invertible systems of linear forms without losing the exponent bounds already obtained. The coefficient form of the Combinatorial Nullstellensatz then produces a common nowhere-zero point. Finally, we test the scope of the theorem. M.~J.~Moghaddamzadeh's unpublished conjecture predicts a stronger statement over prime fields. Projective geometries show that its direct analogue fails over proper extension fields, even under the same numerical inequality.
We prove that for every prime power $q$ and every $p \in (0, 1-1/q)$, a random $\mathbb{F}_q$-linear code of rate $1 - h_q(p) - \epsilon$ is $(p, C_{p,q}/\epsilon)$-average-radius list-decodable with probability at least $1 - q^{-\Omega(n)}$, i.e., for every center $y \in \mathbb{F}_q^n$, the $C_{p,q}/\epsilon$ codewords closest to $y$ have average fractional Hamming distance at least $p$ from $y$. This extends a similar result for (standard) list-decoding due to Guruswami, H\r{a}stad, and Kopparty (2010) to the stronger average-radius guarantee, with the same $O(1/\epsilon)$ list size. For average-radius list-decoding, such a result was previously known only for binary linear codes (Guruswami, Li, Mosheiff, Resch, Silas, and Wootters, 2021) and for general (non-linear) random codes over arbitrary alphabets (Elias, 1991).
V. Guruswami, Shilun Li, Mihir Singhal· 1 citation
This work develops an approach to the spectral norm of the matrix product $\Pi U_V$, based on entropy estimates for level sets of vectors $x\in V$, and shows that matching results hold for other random models with negatively associated entries.
K. Tikhomirov· arXiv.org· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
