CS Paper Radar

$L$-systems on the large Witt design

Toshihiro Shimizu, Norihide Tokushige

cs.IT math.CO ·submitted 2026-11-16 05:31 UTC · v1
theory

Abstract

Let $L=\{0,1,2,3,4,8\}$, associated with the large Witt design $S(5,8,24)$, and let $m(n,24,L)$ be the maximum size of a family of $24$-element subsets of an $n$-element set whose distinct members have intersection sizes in $L$. We prove that there are positive constants $c,C,n_0$ such that, for every $n\geq n_0$, \[ cn^{316/63}\leq m(n,24,L)\leq Cn^{169/29}. \] We also obtain similar results for the systems associated with $S(4,7,23)$, $S(3,6,22)$, and $S(3,4,14)$. The upper bounds follow from a non-Shannon information inequality and disprove conjectures of Kupavskii and Terekhov. The lower bounds follow from an algebraic construction for arbitrary Steiner systems.

Comment
14 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Sharp Bounds for Graph-Codes Avoiding Complete Bipartite Differences

cs.IT math.CO ·2026-10-26 ·Nader H. Bshouty
theory similarity 0.65
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

Almost entropic matroids and $(k,L)$-systems

cs.IT math.CO ·2026-10-20 ·Andrey Kupavskii, Nikolai Terekhov
theory similarity 0.64
Abstract

For an integer $k$ and a set of integers $L$, a $(k,L)$-system is a family of $k$-element sets such that the size of the intersection of any two distinct members belongs to $L$. Let $m(n,k,L)$ denote the maximum size of a $(k,L)$-system on a ground set of $n$ elements. In this work, we establish a close connection between the asymptotic growth of $m(n,k,L)$ and almost entropic matroids. As a consequence, we obtain a general computable upper bound on the asymptotics of $m(n,k,L)$ that unifies and strengthens all previously known upper bounds.

0.48

On Almost MDS codes holding $(n-k-1)$-designs and an open problem on Witt design

cs.IT math.NT ·2026-10-21 ·Huakai Wei, Shiyuan Qiang, Shaofang Hong
similarity 0.62
Abstract · 18 pages

Let $\mathcal{C}$ be an almost maximum distance separable (AMDS) code over the finite fields with parameters $[n,k,n-k]$ whose minimum-weight codewords support an $(n-k-1)$-$(n,n-k,λ)$ design. We first determine the parameters of the dual code $\mathcal{C}^{\bot}$. We also characterize the design and its complementary design supported by the minimum weight codewords of $\mathcal{C}^{\bot}$. In particular, we present explicit formulas for the weight enumerators of all subset codes of $\mathcal{C}^{\bot}$ with length at least $k+1$. These formulas are completely determined by the cardinality of the subset, the dimension, together with the parameter $λ$, and are independent of the specific choice of subsets. As an application, we answer an open problem posed by Wang, Tang and Ding in 2023 by proving that the $3$-design supported by the minimum-weight codewords in their proposed cyclic dual code is isomorphic to the complementary design of the Witt spherical geometry design.

0.28

New lower bounds for constant-weight codes via seeded bit-swap tabu search

cs.IT math.CO ·2026-08-14 ·William Echols
similarity 0.61
Abstract

A binary constant-weight code is a set of binary words of length $n$ such that each word has exactly weight $w$ and is at least Hamming distance $d$ from every other word in the set. $A(n,d,w)$ denotes the maximum size of a binary constant-weight code with parameters $(n,d,w)$. Using seeded initialization with bit-swap tabu search, we found 124 new constructions that improve existing lower bounds for $A(n,d,w)$. As a corollary of stronger bounds on $A(n,8,8)$ for $n \in \{ 32,33,34,37 \}$, we also improve lower bounds on kissing numbers $τ_{32}$, $τ_{33}$, $τ_{34}$, and $τ_{37}$.

0.40

Lower Bounds for all List-Decodable Deletion Codes

cs.IT cs.DMmath.CO ·2026-09-22 ·Andrew D. Lin
theory similarity 0.59
Abstract

A length-$n$ binary $k$-deletion code is a set of binary strings such that if we delete any $k$ bits of a string, leaving a length-$(n-k)$ binary string, we can uniquely recover the codeword. In this paper, we consider $t$-list decodable deletion codes, where after $k$ bits of a codeword are deleted, we can identify a list of size at most $t$ such that the original codeword lies in the list. We prove a lower bound of $Ω_k(2^n t\log^{1/t}n/n^{k+k/t})$ on the optimal size of a $t$-list decodable $k$-deletion code, giving a $\sqrt{\log n}$ improvement over the previously best known bounds for $2$-list decodable $2$-deletion codes [GH21] and providing the first nontrivial lower bound when $t>2$ or $k>2$. Our bound holds for all $t\leq n^k$, showing that $t=Ω(\log n)-$list decodable deletion codes have optimal size $Θ_k(2^n t/n^k)$, asymptotically matching the known upper bound. We also prove upper bounds on the number of common subsequences and common supersequences of a given length for any two binary strings.

0.06

Lower bound on the size of splitting systems

cs.DM math.CO ·2026-11-08 ·Fan Chung, Namiko Matsumoto, Arya Mazumdar
theory similarity 0.58
Abstract · 13 pages

For even $t$ and an $n$-set $X$, an $(n,t)$-splitting system is a family ${\mathbb{B}} \subseteq 2^X$ with the property that for each subset $Y \in {X \choose t}$, there exists $B \in \mathbb{B}$ such that $|B \cap Y| = t/2$. The problem of interest is to determine the minimum size of such splitting systems. We show that any $(n,t)$-splitting system has size at least of order $t$, improving the previous lower bound of $\sqrt t$ while the best known upper bound is of order $t^{3/2}$.

0.30

Mutually orthogonal anti-Latin squares

cs.IT math.CO ·2026-08-30 ·Eishiro Aoyama, So Hasegawa, Masahito Hayashi, Tomoki Sagara
theory similarity 0.57
Abstract

Anti-Latin squares were introduced in connection with non-linear secure network coding, and the extremal problem for large mutually orthogonal families is motivated by that setting. We study the maximum size $N_A(d)$ of a family of mutually orthogonal anti-Latin squares of order $d$. We prove that $N_L(d)+1\le N_A(d)\le N_L(d)+2$ for every $d\ge 3$, where $N_L(d)$ denotes the classical maximum size of a family of mutually orthogonal Latin squares of order $d$, and we show that in fact $N_A(3)=N_L(3)+1$ whereas $N_A(d)=N_L(d)+2$ for every $d\ge 4$. The upper bound is obtained by passing through balanced matrices, while the lower bound is given by a deterministic permutation argument. For all $d\ge 8$, and also for the exceptional order $d=6$, the upper bound is shown to be attainable by a general probabilistic construction. On the structural side, we show that a saturated family of size $d+1$ induces an affine plane of order $d$, and that the saturated case is characterized by the existence of an anti-coordinate grid decomposition; after transporting this condition to the fixed cell set $[d]^2$, it becomes a direction-completeness condition on the corresponding row-blocks and column-blocks. The remaining small orders are treated separately: $d=3$ is handled by direct analysis and classification of orthogonal triples, $d=4$ by an explicit saturated construction and an analysis of its finite-geometric structure, and $d=5$ and $d=7$ by explicit saturated examples arising from the random-grid framework. Thus $N_A(d)$ is determined in terms of $N_L(d)$ for every $d\ge3$, and its numerical value is obtained explicitly for every $3\le d\le9$.

0.25

Generalized Hamming weights of codes arising from complete intersection

cs.IT math.AC ·2026-08-20 ·Eduardo Camps Moreno, Flavio Salizzoni, Rodrigo San-José
similarity 0.57
Abstract · 5 pages

We provide a positive answer to a conjecture proposed by Tohǎneanu and Van Tuyl regarding the minimum distance of codes whose underlying set of points is a reduced complete intersection. Despite the technical nature of the conjecture, we show that it follows directly from a not-well-known refinement of the classical Bézout bound for overdetermined polynomial systems. For completeness, this paper presents a self-contained proof of this refined bound. Furthermore, we show that using the same approach, it is possible to obtain a bound on the generalized Hamming weights of such a code and, more generally, to control the minimum distance of the codes obtained by evaluating forms of degree $d$ on the points of a zero-dimensional complete intersection.

0.33