CS Paper Radar

More lower bounds for Hales--Jewett and van der Waerden numbers

Younes Mouhib

cs.DM math.CO ·submitted 2026-11-17 04:44 UTC · v1
code/data

Abstract

We give explicit colourings improving the comparison lower bounds assembled here for several Hales--Jewett and van der Waerden numbers. The main algebraic tool generalises Rabung's power-residue colouring from arithmetic progressions to arbitrary sets. If every translate of a t-element set S in F_p meets at least two classes of the r-th power character, and the integer weights have both parities, then a period-2p one-weight colouring of [t]^p has no monochromatic combinatorial line. The 19 displayed algebraic certificates comprise 18 improvements and one closed-form reproduction; they include HJ(4,3)>=164, HJ(5,4)>=7418, and HJ(5,6)>=34034. The underlying period-p construction also proves kappa_ow(t,r)>=p-1 for the one-weight bracket ceiling, in particular kappa_ow(5,4)>=7416 and kappa_ow(5,6)>=34032. Warm breakout-weighted tabu search on the type simplex gives HJ(3,4)>=51. Whole-colouring local search gives W(8,3)>522, W(11,3)>1193, and W(17,3)>3620. All accepted certificates are available separately and are checked by direct enumeration; unresolved searches are reported as UNKNOWN, not UNSAT.

Comment
6 pages. Explicit certificates, search algorithms, and verification code are available at https://github.com/ysmouhib/hj-vdw-reproducibility and in the ancillary files

Closest papers

Nearest neighbours by meaning across the whole index.

The Exact Weight Spectrum of $\RM(m-7,m$): A Counterexample to the Carlet-Solé Conjecture

cs.IT ·2026-10-27 ·Yueying Lou, Qichun Wang
similarity 0.59
Abstract

Boolean functions are widely used in cryptography and coding theory. A key challenge lies in finding the weight spectrum for all $n$-variable Boolean functions of degree at most $r$, also known as the Reed--Muller code $\RM(r,n)$. In 2023, Carlet and Solé determined the weight spectra of $\RM(n-c,n)$ for $c=3,4$, and conjectured the weight spectrum of $\RM(n-c, n$) for $n\ge2c$. The weight spectra of $\RM(n-5, n)$ and $\RM(n-6,n)$ were determined by Carlet in 2024 and by Lou and Wang in 2025, respectively, confirming the Carlet-Solé conjecture for the cases $c=5,6$. Very recently, Leuenberger et al. and Wei et al. investigated the weight spectrum of $\RM(7,14)$ independently, and there are eight potential weights which have not been determined. Up until now, the weight spectra of the Reed--Muller codes $RM(r,n)$ are still unknown for $r=3,...,n-7$. In this paper, we determine the exact weight spectrum of $\RM(m-7, m)$ for every $m\ge 14$. By combining affine geometry and Fourier analysis, we exclude the conjectured eight weights for $\RM(7,14)$. We then extend the exclusions to all higher dimensions using a geometric transfer. Consequently, we provide a counterexample to the Carlet-Solé conjecture.

0.13

Some Results on the Weight Spectrum of Binary Reed-Muller Codes $RM(m-7,m)$

cs.IT ·2026-10-21 ·Zibo Wei, Bo Zhou, Xiao Zhang, Hao Chen
theory similarity 0.59
Abstract · 36 pages

We study the set of weights occurring in the high-order binary Reed-Muller codes $RM(m-7,m)$. For every $m\geq 14$, we prove that the weight spectrum contains all even weights in $[336,2^m-336]$, together with an explicit finite set of low weights and their complements. The proof first establishes the corresponding base-code inclusion in $RM(7,14)$. This base step uses four-block concatenation, explicit degree-six monomial witnesses, and known spectrum inputs for $RM(5,10)$ and $RM(6,12)$. The base inclusion is then lifted to all $m\geq 14$ by a concatenation-based induction. We also analyze the remaining base-code target weights $322,326,330,334$ in several restricted families, including four-block branches, affine-flat and structured inner corrections in a fixed Carlet-type Maiorana-McFarland outer shell, and sparse sums of degree-7 coordinate monomials. The residual analysis delineates several construction routes that cannot yield the four unresolved base-code weights, thereby sharpening the remaining $c=7$ spectrum problem.

0.47

Explicit Edit Codes via Multicoloring

cs.IT cs.DMcs.DS ·2026-11-12 ·Huiling Xie, Zitan Chen
similarity 0.59
Abstract

For any fixed integers $q\ge2$ and $t\ge1$, we construct explicit $q$-ary codes of length $n$ that correct any combination of at most $t$ insertions, deletions, and substitutions, with redundancy at most $2t\log_q n+O_{q,t}(\log\log n)$ $q$-ary symbols. This matches the leading redundancy term of Levenshtein's classical existential bound. Building on the standard graph-coloring approach, we use a prime-based multicoloring of the edit-confusion graph to assign multiple colors to each $q$-ary word of length $m<n$. Appending a short, edit-protected representation of an assigned color to the length-$m$ word yields a length-$n$ codeword. The choice among the assigned colors carries additional message information, thereby reducing the redundancy. The construction admits deterministic encoding and decoding in $\widetilde O_{q,t}(n^{6t+2})$ and $\widetilde O_{q,t}(n^{7t+2})$ time, respectively.

0.09

Reed-Muller Codes are Optimal Binary Linear 3-Query LCCs

cs.IT cs.CCmath.CO ·2026-11-02 ·Oliver Janzer, Peter Manohar
theory similarity 0.57
Abstract

We prove that any linear $3$-query locally correctable code $C \colon \mathbb{F}_2^k \to \mathbb{F}_2^n$ with constant correction radius must have length $n \geq 2^{Ω(\sqrt{k})}$. This improves on the prior best lower bound of $2^{Ω(\sqrt{k/\log k})}$, due to [AG24], and shows that the folklore construction of linear $3$-LCCs from Reed-Muller codes, which achieve length $n = 2^{O(\sqrt{k})}$, is optimal up to constant factors in the exponent. Our proof builds on the approach of [KM24a], further refined in [Yan24,KM24b], that uses "chain derived equations" in combination with Kikuchi graphs. The crux of our argument is to show that a certain edge-coloured Kikuchi graph has a unique colour cycle: a cycle in which some colour is used exactly once. We do this by controlling the distribution of colours at each vertex in the graph using a random walk mixing argument and a novel hypergraph decomposition based on edge expansion of the hypergraph's "flattening" into a graph.

0.42

Six Families of Binary Codes Arising from Ding's Conjectures

cs.IT ·2026-09-29 ·Xiaoqiang Wang, Shiyan Xiong, Mu yuan, Jing Qiu, Dabin Zheng +1 more
theory similarity 0.56
Abstract

Ding \cite{Ding2016} proposed ten conjectures on binary linear codes arising from Boolean functions. Four of them, namely Conjectures 38--41, were subsequently proved by Göloğlu and Krasnayová \cite{GologluKrasnayova2019}. In this paper, we investigate the remaining six conjectures, namely Conjectures 19, 27, 30, 33, 34, and 37. For Conjectures~19 and~27, we obtain common weight restrictions and several infinite five-weight families. For Conjecture~30, we prove that every admissible code has three, four, or five nonzero weights, and an explicit four-weight example disproves the original ``three or five weights'' assertion. For Conjecture~33, an infinite five-weight family is obtained. For Conjecture~34, we obtain a general $(2h+1)$-weight upper bound and give an explicit six-weight counterexample, showing that the original ``three or five weights'' assertion is false in general, where $h$ is a positive integer. The case $h=3$ with $3\nmid m$ is also completely determined. Finally, Conjecture~37 is completely resolved by combining the known results of Ahmadi and Shafaeiabr \cite{AhmadiShafaeiabr2023} with the treatment of the two remaining classes $(a)$ and $(b)$.

0.04

The weight enumerators of irreducible cyclic codes of length $2^\ell$

cs.IT math.CO ·2026-10-08 ·Ricardo A. Podestá, Denis E. Videla
similarity 0.56
Abstract · 19 pages, 3 tables

Using the spectral relation between irreducible cyclic codes (ICC) and generalized Paley (GP) graphs recently found by the authors, we study the weight distribution of irreducible cyclic codes of length $2^\ell$, $\ell \in \mathbb{N}$. These codes were previously studied by Sharma, Bakshi and Raka, who divided them into two families (each having two cases). First we characterize the GP-graphs spectrally related to these families of ICCs: they are complete, semiprimitive, Hamming, or Cartesian products of semiprimitive GP-graphs. We then compute the spectrum of these graphs and hence, by the mentioned spectral relation we finally obtain neat explicit expressions for the weight enumerators of all the irreducible cyclic codes of length $2^\ell$ with $\ell \in \mathbb{N}$.

0.11

A Characterization of $q$-Ary $2$-Designs and a $3$-Design Obstruction for Doubly-Extended Reed-Solomon Codes

cs.IT ·2026-11-08 ·Guanghui Zhang, Zhengbang Zha
theory similarity 0.56
Abstract · 18 pages

Let $\mathcal{C}_k$ be the doubly extended Reed--Solomon code with parameters $[q+1,k,q-k+2]_q$, where $q\ge3$ is a prime power and $2\le k\le q$. We prove a conjecture of Wu and Zhou by showing that the minimum-weight codewords of $\mathcal{C}_k$ do not form a $q$-ary $3$-design when $2\le k\le q-1$. Using shortening, we extend this obstruction to every nonempty weight class with $3\le w<q+1$. We also establish that each individual nonempty positive-weight class of $\mathcal{C}_k$ forms a $q$-ary $2$-design if and only if $\gcd(k-1,q-1)=1$. Consequently, every nonempty positive-weight class below full support has exact $q$-ary design strength $2$ when this coprimality condition holds, and $1$ otherwise.The three-design obstruction follows by applying a classical subset-product character identity to a marginal covering count for three prescribed nonzero symbols. The comparison between weights rests on a covering-count formulation of the classical MDS coset-weight relations. For every linear $[n,k,d]_q$ MDS code with $2\le k\le n-1$, this formulation shows that the $q$-ary $2$-design property at any one nonempty positive weight is equivalent to the same property at every nonempty positive weight.More generally, for $2\le t\le\min\{k,d\}$, we prove that the $q$-ary $t$-design property at any $t-1$ distinct nonempty positive weights forces it at all nonempty positive weights.

0.07

Distributed $(Δ+1)$-Coloring in $O(\sqrtΔ+\log^* n)$ Rounds

cs.DS cs.DC ·2026-10-12 ·Marc Fuchs, Fabian Kuhn
theory similarity 0.56
Abstract

We give a deterministic distributed algorithm for $(Δ+1)$-coloring an $n$-node graph of maximum degree $Δ$ in $O(\sqrtΔ+\log^* n)$ rounds in both the LOCAL and CONGEST models. More generally, $(°+1)$-list coloring with lists from a color space of size $C\geqΔ+1$ can be solved in $O(\sqrtΔ\log(1+C/Δ)+\log^* n)$ rounds; in CONGEST, we assume $C\leq n^{O(1)}$. The algorithm combines Barenboim's polynomial coloring procedure with arbdefective decompositions, degree reduction, and a short family of hash functions. Using the polynomial procedure in the degree-reduction framework already gives an $O(\sqrtΔ\logΔ+\log^* n)$-round algorithm when $C=O(Δ)$. Hashing adapts the color space to the current degree and removes the logarithmic factor. We prove the existence of the hash family by the probabilistic method and compute it by deterministic exhaustive search, using unrestricted local computation. We also give an explicit variant based on lossless expanders that avoids this search and achieves $O(\sqrtΔ+\log^* n)$ rounds for $C=O(Δ)$.

0.19