CS Paper Radar

A $G$-Invariant Erdős--Hanani Theorem with Applications to Optical Orthogonal and Constant-Weight Codes

Yeow Meng Chee

cs.IT math.CO ·submitted 2026-10-07 22:52 UTC · v1
theory

Abstract

Let $k>t\ge 2$ be fixed integers, and let $G$ be a permutation group on a set of $v$ points. A $G$-invariant packing is free if every block has $|G|$ distinct images under $G$. We give two conditions on $G$ under which, as $v\to\infty$, there is a free $G$-invariant $t$-$(v,k,1)$ packing with $(1-o(1))\binom{v}{t}/\binom{k}{t}$ blocks. This is a $G$-invariant form of the Erdős--Hanani theorem on asymptotically optimal packings. For semiregular groups $G$, packings with these properties exist if and only if all but $o(v^t)$ of the $t$-subsets of points have trivial setwise stabiliser. This property is satisfied by every semiregular group for $t\ge 3$, and by every cyclic semiregular group for $t=2$. As a consequence, the Johnson bound is asymptotically attained at all lengths by optical orthogonal codes of constant weight $w$ and constant correlation $λ$ with $w\geλ+2$, by their multidimensional and signature pattern versions, and by cyclic and quasi-cyclic constant-weight codes. The same method gives a form of the theorem for group divisible packings that are invariant under a cyclic group. This determines the asymptotic maximum size of two-dimensional optical orthogonal codes with at most one pulse per wavelength.

Comment
16 pages, 1 table

Closest papers

Nearest neighbours by meaning across the whole index.

The Optimal Asymptotic Rate of Generalized Covering Codes

cs.IT ·2026-08-25 ·Hengzhuo Li, Chong Shangguan, Hengjia Wei
theory similarity 0.60
Abstract · 18 pages

Let $G_q$ be an alphabet of size $q\geq2$. We determine the optimal asymptotic rate of generalized covering codes $C\subseteq G_q^n$, whose covering centers in $G_q^{t\times n}$ are constrained to the product form $C^t$. For every fixed integer $t\geq1$ and every $ρ\in[0,1]$, we prove that \[ κ_t(ρ,q)= \begin{cases} 1-H_{q^t}(ρ),&0\leqρ<1-q^{-t},\\ 0,&1-q^{-t}\leqρ\leq1, \end{cases} \] where $κ_t(ρ,q)$ denotes the minimum asymptotic rate $n^{-1}\log_q|C|$ among codes whose $t$-th covering radius is at most $ρn$, and $H_{q^t}$ is the $q^t$-ary entropy function. When $q$ is a prime power, we prove that the same formula holds under the additional requirement that $C\leq\mathbb F_q^n$. Thus, both the product-form constraint and linearity are asymptotically cost-free: the resulting rate is the ordinary sphere-covering rate over an alphabet of size $q^t$. This extends the recent $t=2$ result of Elimelech and Schwartz for codes without a linearity constraint and the classical $t=1$ result of Cohen and Frankl for linear codes, thereby resolving both open problems posed by Elimelech and Schwartz. Our proofs are probabilistic and combine tools from information theory and probabilistic combinatorics, including the method of types, Janson's inequality, the second-moment method, and a structured alteration argument. Direct applications of Janson's inequality and the second-moment method are obstructed by highly dependent pairs of candidate error matrices. We overcome this obstruction by restricting the errors to a balanced exact-type class of optimal exponential size. Standard type-class estimates, together with Shearer's inequality, then give the required bounds on the number of error-matrix pairs whose selected rows have a prescribed difference.

0.38

Replica Thresholds for Stripeless Erasure Coding Based on Symmetric Block Designs

cs.IT ·2026-09-24 ·Guiwen Luo, Xiao Li, Yaqiang Zhang, Ke Wang
similarity 0.60
Abstract

This paper investigates a fundamental question in stripeless erasure coding based on symmetric balanced incomplete block designs (SBIBDs): how many replicas per object are precisely required to guarantee recovery from any set of at most $p$ node failures? We refine the known sufficient recovery guarantee for the generalized SBIBD $(v,k,λ)$ construction. One replica is necessary and sufficient for $p=1$, and $q=λ(p-1)+2$ replicas ($q\le k$) guarantee recovery for $p\ge2$. Recovery takes one round for $p=2$ and at most two rounds in general. To study the tightness of this count, we define the universal replica threshold $q^\ast(A,p)$ for a fixed zero-diagonal SBIBD representative~$A$. We determine $q^\ast(A,p)$ for $p=1$ and $p=2$. For $p\ge3$, we identify pairwise separated sets and private target permutations as the structures determining whether the sufficient count is tight or can be further reduced. These conditions give exact thresholds for all but the case where $λ>1$ and $A$ contains no pairwise separated set of size~$p$. We improve the bounds for this remaining case and leave its exact threshold open. Finally, we give sufficient conditions for pairwise separated sets and show how affinity relabeling can realize private target permutations.

0.29

Evasive subspaces, minimal rank-metric codes and subspace designs via auxiliary fields

cs.IT math.CO ·2026-11-05 ·Alessandro Giannoni
similarity 0.58
Abstract · 33 pages

We extend the auxiliary-field method for scattered subspaces to evasive subspaces and subspace designs. For $1\le h\le k<hn$ and coprime $h,k+1$ with $n(k-h+1)\ge k+1$, we construct spanning $(h,k)$-evasive $\mathbb{F}_q$-subspaces of $\mathbb{F}_{q^n}^r$ of dimension $rn(k-h+1)/(k+1)$ in every sufficiently large admissible ambient dimension, with a threshold independent of $q$. When $k<n$, this dimension is maximum. The proof combines an intersection lemma, a rank-support density inequality, scalar orbit counting, and a profile preserved by direct sums. The coding consequences include, for every fixed odd extension degree $m\ge3$ and every sufficiently large $K$, minimal rank-metric codes of optimal length $2K$ with first two generalized weights $(m+1)/2$ and $m+1$. For these codes the stable profile is equivalent to minimality with the largest possible minimum distance; for even $m$ the analogous class consists of minimal MRD codes. More generally, for $1\leτ\le m-2$ and $\gcd(m,τ+1)=1$, we obtain nondegenerate $τ$-minimal codes of length $(τ+1)K$ for every sufficiently large $K$, uniformly in $q$. We also construct maximum $h$-designs whose number of members grows exponentially with the ambient dimension at fixed $q,n,h$, and the associated maximum sum-rank distance (MSRD) codes with a growing number of equal long blocks. In extension degree five, the ordinary and $2$-minimal constructions hold for every $q$ and every $K\ge32$ and $K\ge59$, respectively.

0.09

Subspace coverings and generalized covering radii of generalized Zetterberg codes

cs.IT math.CO ·2026-09-20 ·Shitao Li, Yang Li, Gaojun Luo, Zhonghua Sun
theory similarity 0.58
Abstract

Generalized covering radii measure how many columns of a parity-check matrix are needed to generate several syndromes simultaneously. Their finite-geometric counterparts are $(ρ,t)$-saturating sets, for which every $t$-dimensional subspace is contained in a subspace generated by at most $ρ$ prescribed vectors. We investigate this covering problem for the norm-one configurations associated with generalized Zetterberg codes. We establish the upper bound $2t+1$ over every nonbinary finite field and in an explicit binary range, together with complementary lower bounds obtained by counting subspaces and constructing subfield obstructions. For an explicit range of large $t$, these configurations are $t$-strong blocking sets, and the $t^{\rm th}$ generalized covering radius attains its minimum possible value $t$. For binary Zetterberg codes, we determine the second generalized covering radius in every extension degree and prove that the third radius is seven for an infinite subfamily.

0.36

Sharp Bounds for Graph-Codes Avoiding Complete Bipartite Differences

cs.IT math.CO ·2026-10-26 ·Nader H. Bshouty
theory similarity 0.57
Abstract

Let $d_{K_{s,t}}(n)$ be the largest fraction of all graphs on $[n]$ in a family containing no two distinct members whose symmetric difference is a copy of $K_{s,t}$. We determine this maximum density for every fixed pair of positive integers $s,t$. If both part sizes are odd, it is known that the density is exactly $1/2$. Otherwise, let $2h$ be the largest even part size. We prove $$ d_{K_{s,t}}(n)=Θ_{s,t}(n^{-h}). $$ For $h>1$, this improves the general $O_{s,t}(1/n)$ upper bound obtained from Alon's two-copy gluing theorem~\cite{Alon2024}. The sharp bounds for even stars were already proved by Alon and are recovered as special cases. The upper bound uses the Frankl--Füredi forbidden-intersection theorem. For the lower bound, we construct binary linear codes using BCH codes. When exactly one part size is even, we assign to each edge the sum of the binary vectors assigned to its endpoints. When both part sizes are even, we identify these vectors with elements of a finite field and assign to each edge the product of its endpoint elements. In both cases, every copy of $K_{s,t}$ has a nonzero syndrome.

0.27

Random Non-Commutative Error-Correcting Codes

cs.IT math.GR ·2026-10-28 ·Michael Best, Alexander Lubotzky
similarity 0.57
Abstract · 18 pages, 1 table

Chapman, Dinur, and Lubotzky recently introduced the theory of non-commutative error-correcting codes, generalizing classical coding theory to arbitrary groups via $δ$-robust subsets used to detect proper subgroups. Building on this foundation, this paper systematically studies an analogue of random codes for arbitrary groups, exploring the extent to which the classical Gilbert-Varshamov (GV) bound holds in this non-commutative setting. While random universal codes of linear size in free groups are shown to be asymptotically bad, we establish a complete characterization for general families of finite groups. Specifically, a family of finite groups admits good random codes (forming a GV family) if and only if it exhibits uniform polynomial maximal-subgroup growth. Furthermore, we provide explicit quantitative bounds on the rate and optimal distance range based on intrinsic parameters, proving that families of finite solvable groups always form GV families and determining the exact probabilistic rate for direct powers of a fixed finite simple group.

0.25

A Note on Sphere Packing Bounds for Tuple Lattice Sieving

cs.CR math.COcs.ITmath.MG ·2026-09-08 ·Thijs Laarhoven
similarity 0.56
Abstract · 6 pages, 1 figure

A finite set of unit vectors is $k$-irreducible if every signed sum of between two and $k$ distinct elements has norm greater than one. Let $\mathcal{R}_k$ be the maximal asymptotic rate of such sets, and let $κ(α)$ be the maximal asymptotic rate of spherical codes with pairwise inner products at most $α$. For $k \ge 2$ we show: \begin{align} \mathcal{R}_k \le \min_{1 \le r \le \lfloor k/2 \rfloor} \frac{1}{r} \, κ\!\left(1 - \frac{1}{2r}\right) \, . \end{align} Combining this with standard sphere packing bounds, for large $k$ we obtain an almost-tight asymptotic comparison with the known lower bounds: \begin{align} \left(\tfrac{1}{2}-o(1)\right) \, \frac{\log_2 k}{k} \le \mathcal{R}_k \le (1 + o(1)) \, \frac{\log_2 k}{k} \, . \end{align}

0.24

An Erdős-Pósa theorem for induced packings of even cycles

cs.DM math.CO ·2026-10-16 ·Jungho Ahn, Lars Jaffke, O-joung Kwon, Paloma T. de Lima, Hyemi Park
theory similarity 0.55
Abstract · 38 pages, 5 figures

We show that for every graph $G$ and every positive integer $k$, $G$ contains either $k$ vertex-disjoint even cycles with no edges between distinct cycles, or a set of $O(k^2\log k)$ vertices whose closed neighborhood meets every even cycle of $G$. Moreover, we give a polynomial-time algorithm that outputs one of the two outcomes. As an application, we show that every $K_{1,t}$-free graph containing no induced packing of $k$ even cycles has tree-independence number $O(tk^2\log k)$, with a corresponding decomposition computable in polynomial time.

0.10