CS Paper Radar

The fourth generalized Davenport constant of $C_5^3$

Sze Chun Yiu

cs.DM math.CO ·submitted 2026-09-04 09:55 UTC · v1
theory

Abstract

For a finite abelian group $G$ and $k \geq 1$, the generalized Davenport constant $D_k(G)$ is the least $\ell$ such that every sequence over $G$ of length at least $\ell$ has $k$ pairwise disjoint nonempty zero-sum subsequences. A theorem of Freeze and Schmid gives $D_k(C_5^3) \geq 5k+10$ for every $k \geq 2$. We prove the matching upper bound: $D_4(C_5^3)=30$, and hence $D_k(C_5^3)=5k+10$ for every $k \geq 2$, so the Freeze--Schmid bound is attained by $C_5^3$ from $k=2$ onward, as it is by $C_2^3$ and unlike $C_3^3$. The proof is finite and computer-assisted. The remaining case reduces to showing that every zero-sum sequence of length $31$ over $C_5^3$ contains a nonempty zero-sum subsequence of length at most five. A saturation argument confines the multiplicities of a hypothetical counterexample to $\{1,2,4\}$, its support pattern to one of $60$ solutions of two linear equations, and its geometry to one of $78$ rank/plane branches normalized to a standard basis; an exhaustive search exhausts every branch with no survivor. The search was carried out by three independently written implementations, and the branch cover was regenerated by separate programs from the lemmas alone; two further machine-verified values, $D_3(C_5^3)=25$ and $s_{\leq 6}(C_5^3)=24$, enter the second statement, and their records accompany the paper.

Comment
13 pages; computer-assisted proof; ancillary computational verification files included

Closest papers

Nearest neighbours by meaning across the whole index.

A new lower bound for the sixth Schur number: $S(6)\ge 537$

cs.DM math.CO ·2026-10-22 ·Zhiyang Chen, Ligeng Zhu, Fan Long
theory similarity 0.55
Abstract

We give an explicit partition of $\{1,\ldots,537\}$ into six sum-free sets, establishing $S(6)\ge 537$. This improves the lower bound 536 of Fredricksen and Sweet (2000). Known recursive constructions then give the improved lower bounds $S(8)\ge 5\,372$, $S(11)\ge 204\,208$, $S(13)\ge 2\,042\,082$, and $R_6(3)\ge 539$. We also report 131 pairwise inequivalent partitions found by the search. We describe their structure and provide the complete partitions in the supplementary material. These partitions provide starting points for future searches and structural studies of Schur partitions.

0.27

Word Length and Diameter in Permutation Groups

cs.CC math.GR ·2026-09-22 ·Markus Lohrey, Alexander Thumm
similarity 0.54
Abstract

In the binary diameter problem, the input consists of explicitly given permutations generating a finite group $G$ and a binary-encoded number $k$, and the question is whether every element of $G$ is a product of at most $k$ of the given generators. In the binary length problem, the input additionally contains a permutation $g \in G$, and the question is whether $g$ is such a product. We show that the binary diameter problem is PSPACE-complete, thereby confirming a conjecture of Lohrey and Rosowski (2023). Moreover, we show that PSPACE-hardness already holds for solvable groups of derived length at most 3, whereas the problem is $Π_2^{\mathrm{P}}$-complete for 2-step nilpotent groups. For the binary length problem, we establish a sharp complexity threshold: the problem is NP-complete for 2-step nilpotent groups, which extends a result of Lohrey and Rosowski for abelian groups, and PSPACE-complete for groups that are simultaneously 3-step nilpotent and metabelian, which strengthens the main result of Jerrum (1985). Finally, we show that the unary diameter problem, where $k$ is encoded in unary, is $Π_2^{\mathrm{P}}$-complete for generating sets of the full symmetric group, confirming another conjecture of Lohrey and Rosowski.

0.28

The Ternary and Quaternary Cases of the $\{2,4\}$-Distance Code Conjecture

cs.IT math.CO ·2026-10-22 ·Yen-Chi Roger Lin, Valjakas Djaljapayan, Wei-Hsuan Yu
theory similarity 0.54
Abstract

For an integer $q\ge2$, let $A_q(n,\{2,4\})$ be the largest cardinality of an unrestricted $q$-ary code of length $n$ in which any two distinct words have Hamming distance $2$ or $4$. We prove that \[ A_q(n,\{2,4\})=1+\binom n2 \qquad(q\in\{3,4\},\ n\ge6), \] thereby settling the two remaining alphabet sizes in the conjecture of Boyvalenkov, Delchev, Zinoviev, and Zinoviev; the binary case was settled previously. The quaternary result implies the ternary result by alphabet inclusion. For $n\ge16$, the quaternary upper bound is proved combinatorially. After normalizing one word to zero, the weight-four supports form a $2$-intersecting family; exact support intersections force symbol synchronization and restrict support multiplicities. We combine the nontrivial intersection theorem with matching arguments and a three-coordinate projection lemma. The finite lengths $6\le n\le13$ are handled by a complete Hamming-isometry reduction to exact clique decisions, and $n=14,15$ by a smaller exact weighted-clique relaxation. All finite decisions are reproduced by two standalone integer-only C++17 verifiers provided as supplementary source files.

0.20

Exact guarantees and faster algorithms for $k$-rollercoasters

cs.DM cs.DS ·2026-11-19 ·Sungmin Kim, Florin Manea
theory similarity 0.53
Abstract

For $k\ge3$, a $k$-rollercoaster is a sequence of distinct values whose maximal increasing and decreasing runs all have length at least $k$. We discover the maximum guaranteed length $f_k(n)$ of $k$-rollercoasters appearing as subsequences of $n$-point permutations. In particular, letting $q=k-1$, we prove that $f_k(n)= \lceil n/q\rceil$ for $n\ge2q^2$, $f_k(n)= 2q-\lfloor \sqrt{2q^2-n}\rfloor$ for $q^2<n<2q^2$ and $f_k(n)= 0$ otherwise. We prove that the guarantees are tight by constructing an $n$-point permutation whose longest $k$-rollercoaster has exactly $f_k(n)$ points. Our proof extends Seidenberg's argument [Journal of the London Mathematical Society, 1959] for proving the Erdős--Szekeres theorem by representing points in a subsequence with respect to the lengths of longest monotonic (increasing and decreasing) subsequences that reach each point. The combinatorial proof yields a deterministic comparison-based algorithm that finds a rollercoaster of length at least $f_k(n)$ in $O(n\log f_k(n))$ time and $O(n)$ space for $n>q^2$. Independently, we give an $O(nk\log k)$-time, $O(nk)$-space algorithm for a longest $k$-rollercoaster, improving the previous $O(nk^2)$ bound. We use the dynamic program of Gawrychowski et al. [STACS 2019, Algorithmica 2022], and process its weighted predecessor queries through monotone subsequences with finger-search trees. Both algorithms return such subsequences.

0.37

Improved bounds for the smallest 4-chromatic graph of girth six

cs.DM math.CO ·2026-08-24 ·Glauco Rampone
theorycode/data similarity 0.52
Abstract · 12 pages, 1 figure. Ancillary files: independent verification scripts, SAT certificates, and a self-contained Lean 4 formal proof. Code and …

For integers $k,g \ge 3$ let $n_g(k)$ denote the minimum order of a graph with chromatic number $k$ and girth at least $g$. Exoo and Goedgebeur (DMTCS 2019) proved $26 \le n_6(4) \le 66$; their 66-vertex witness has remained the smallest known 4-chromatic graph of girth 6. We improve both bounds to $29 \le n_6(4) \le 64$. The upper bound is witnessed by an explicit 4-chromatic graph of girth 6 on 64 vertices with 152 edges; it is vertex- and edge-critical, and its automorphism group is cyclic of order 8 and acts semiregularly. The lower bound is an exhaustive isomorph-free computation in the SAT modulo symmetries framework with co-certificate learning, driven by the Liu-Postle edge-density bound for 4-critical graphs of girth five; it re-derives $n_6(4) \ge 26$ by a disjoint method and is validated on the known values $n_4(4)=11$ and $n_5(4)=21$. We complement the bounds with structural obstructions: no smaller witness arises from either known witness by local modifications; no 4-chromatic Cayley graph of girth 6 exists on 54-63 vertices (for orders 59 and 61 no vertex-transitive witness exists at all); and no witness on at most 63 vertices admits a semiregular automorphism group with two or three vertex orbits, for any finite group. Since every known witness of an $n_g(4)$ record with $g \ge 6$ is a lift of a small base graph along a semiregular action, these results close the most symmetric part of that regime below 64 vertices. All properties of the new graph are verified by independent programs and formally certified in the Lean 4 proof assistant: the non-3-colourability is established inside Lean by a formally verified checker that re-validates a 219,532-node refutation certificate, with a machine-checked soundness theorem.

0.39

Energy Estimation of the Hamming Slice and its Applications

cs.IT math.CO ·2026-09-07 ·Aniruddha Biswas, Jihun Hwang, Hemanta K. Maji, Ilya D. Shkredov, Xiuyu Ye
theory similarity 0.51
Abstract

Let $R=\mathbb{Z}/(2^n-1)\mathbb{Z}$, where $n\geq 3$, and let $S_w\subseteq R$ be the residues whose canonical $n$-digit binary expansion has Hamming weight $w$. We obtain, in particular, an asymptotic formula for the additive energy of $S_w$ \[ E(S_w)=\frac{\left|S_w\right|^4}{|R|}+ \mathcal{O}\left(|R|^3 n^{-3} \right), \] which holds uniformly in $w$. The error term is optimal in order, with a matching lower bound for $w=\lfloor n/2+\sqrt{n} \rfloor$. It follows that triple sums of arbitrary unit dilates have asymptotically uniform representation counts when $\prod_{j=1}^{3} \left|S_{w_j} \right| /\left(|R| n^{-3/5}\right)^3\to\infty$, and that double sums have asymptotically full support when $\left|S_{w_1}\right| \left|S_{w_2} \right|/\left(|R| n^{-3/4}\right)^2\to\infty$. In the proof, modular collisions are represented using a cyclic binary carry automaton; this appears to be a novel approach in this area of problems.

0.43

Improved Subexponential Upper Bounds for $3$-Restricted Matching Vector Families

cs.CC cs.DMcs.IT ·2026-08-28 ·Sidhant Saraogi
publishedtheory similarity 0.51
Abstract · 11 pages

Matching Vector families (MVFs) are defined by two ordered lists of vectors in $\mathbb{Z}_m^n$ whose inner products satisfy specific residue patterns modulo an integer $m$. Most famously, restricted MVFs are used to construct the best-known constant-query Locally Decodable codes (LDCs). We prove an upper bound of $2^{O\left(\sqrt{n\log n \log m}\right)}$ on the size of $3$-restricted MVFs in $\mathbb{Z}_m^n$ for $m \leq \sqrt{n}$, substantially improving on the previous best bound of $2^{O(n/\log n)}$ by Bhowmick, Dvir and Lovett (STOC'13, SICOMP'14). Our proof relies on a new polynomial method argument that controls collisions in sumsets of matching vectors.

0.27

An Improved Upper Bound for the Turán Number of the Hexagon

cs.DM math.CO ·2026-09-09 ·Sandip Das, Sk Samim Islam, Aashirwad Mohapatra, Saumya Sen
theory similarity 0.51
Abstract · 9 pages

For a graph $F$, the Turán number $\operatorname{ex}(n,F)$ is the maximum number of edges in an $n$-vertex graph containing no copy of $F$. Determining the Turán numbers of even cycles is a central problem in extremal graph theory and remains open in general. For $C_6$, the best previous upper bound was due to Füredi, Naor, and Verstraëte [Advances in Mathematics, 2006], who proved that, for sufficiently large positive integer $n$, $$ \operatorname{ex}(n,C_6) \leq λn^{4/3}+O(n)<0.6272 n^{4/3}, $$ where $λ$ is the real root of $ 16λ^3-4λ^2+λ-3=0$. We improve this bound by showing that, for sufficiently large positive integer $n$, $$ \operatorname{ex}(n,C_6) \leq αn^{4/3}+O(n)<0.6144 n^{4/3}, $$ where $α$ is the unique real root of $ 4 α^{3} (3/2)^{1-1/(2α)} =1$ in the interval $(1/2,2/3)$.

0.27