CS Paper Radar

Comments on "Multidimensional Costas Arrays and Their Periodicity"

Shiv Munagala

cs.IT math.CO ·submitted 2026-10-25 20:05 UTC · v1

Abstract

Rubio and Torres conjectured that a multidimensional Costas array, defined by a bijection between two boxes of integer points whose domain has at least as many dimensions as its image, can stay Costas in every window of its periodic extension only if its order is a power of two fixed by the dimension of the domain. We give a four-dimensional periodic Costas array of order $6$, with a two-dimensional domain and a two-dimensional image, so the conjecture is false. The verification reduces to $36$ windows. It has been confirmed by computer and in the Lean proof assistant. The array also meets with equality the pigeonhole bound that Rubio and Torres use for their non-existence results, so that bound is tight.

Comment
Comment arXiv:2208.02378

Closest papers

Nearest neighbours by meaning across the whole index.

Some results on Archdeacon's conjecture for rotation systems

cs.CG math.CO ·2026-09-10 ·Arahat Chikkatur, Ji Zeng
theory similarity 0.57
Abstract

A rotation system on $n$ elements assigns to each element a cyclic order of the other $n-1$ elements. A four-element subset is non-planar if its induced rotation system cannot be realized by a crossing-free drawing of $K_4$. As a combinatorial strengthening of Hill's conjecture on the crossing number of the complete graph, Archdeacon conjectured that every rotation system on $n$ elements has at least $H(n)=\frac{1}{4} \lfloor\frac {n}{2}\rfloor \lfloor\frac{n-1}{2}\rfloor \lfloor\frac{n-2}{2}\rfloor \lfloor\frac{n-3}{2}\rfloor$ non-planar four-element subsets. We computationally verify Archdeacon's conjecture for $n\leq 10$ and show that every extremal rotation system in these orders is realizable by a simple drawing. With computer assistance, we prove that every rotation system on $n$ elements has at least $(8/9 - o(1)) H(n)$ non-planar four-element subsets. We also present a proof by hand for a weaker lower bound of $(2/3-o(1)) H(n)$. Finally, extending recent work of Felsner on antipodal pairs in drawings, we show that Archdeacon's conjecture holds for antipodally shellable rotation systems.

0.39

$k$-arrangements of pseudolines and pseudocircles

cs.CG math.CO ·2026-09-30 ·Jan Kynčl, Carolina Medina, Gelasio Salazar
theory similarity 0.56
Abstract · 19 pages, 10 figures

A $k$-arrangement of pseudolines is a set of bi-infinite curves in the plane such that any two of them intersect each other in exactly $k$ points, at which they cross, and it is simple if no three curves meet at a common point. Cyclic arrangements are the only simple $1$-arrangements of pseudolines that are unavoidable, in the Ramsey spirit: for each fixed $m\ge 1$, every sufficiently large simple $1$-arrangement of pseudolines has a cyclic subarrangement of size $m$. We show that, for every $m\ge 3$, the number of unavoidable simple $k$-arrangements of pseudolines of size $m$ grows exponentially with $k$, independently of $m$. For even $k$, we prove an analogous result for $k$-arrangements of pseudocircles.

0.27

Optimal Ordering-Free Two-Dimensional Insdel Reed-Solomon Codes via Cross-Ratios

cs.IT ·2026-11-16 ·Runqing Qiu, Shixin Zhu, Yang Li, San Ling
similarity 0.55
Abstract · 16 pages

Insertion-deletion (insdel) codes correct synchronization errors. By the half-Singleton bound, an ${[n,2]}_q$ code has minimum insdel distance at most $2n-4$. The smallest field size of two-dimensional Reed--Solomon (RS) codes attaining this bound is $Θ(n^3)$. Unlike the minimum Hamming distance, the minimum insdel distance of an RS code depends on the ordering of its evaluation points. An evaluation set is called ordering-free if every ordering of its points gives an RS code attaining the half-Singleton bound. In this paper, we first show that for $n\ge6$ every ${[n,2]}_q$ code attaining the half-Singleton bound is an RS code, and hence $q\ge\binom{n}{3}+2$. Secondly, we show that an ordering-free evaluation set with $n\ge6$ points in $\mathbb{F}_q$ satisfies $n<q^{1/3}+2$, and that it has at most $r+1$ points if $q=r^3$ for a prime power $r\ge3$. Finally, by using cross-ratios, we construct an ordering-free evaluation set with $r+1$ points in $\mathbb{F}_{r^3}$ for every prime power $r$. Hence, the bound $r+1$ is attained for $r\ge3$. Moreover, the constructed set is even robust against permutations combined with insdel errors.

0.14

Dimension Amplification for Tarski Fixed-Point Query Lower Bounds

cs.CC ·2026-10-05 ·Boyu Liu, Zihe Wang
theory similarity 0.55
Abstract · 22 pages

We prove that finding a fixed point of a monotone map on the nine-dimensional grid $[N]^9$ requires $Ω((\log N)^3)$ deterministic queries, even when the fixed point is unique and each query returns the entire function value. The proof gives a construction that raises the dimension from $d$ to $4d+1$, preserves uniqueness, and adds a logarithmic factor to the lower bound. Iteration gives $Ω((\log N)^{r+2})$ queries in dimension $(7\cdot4^r-1)/3$, for every fixed nonnegative integer $r$, with an implicit constant that may depend on $r$. Consequently, no finite logarithmic exponent bounds the query complexity in all fixed dimensions.

0.45

Guillotine and Tiling Cofiniteness in Unary Picture Languages

cs.FL ·2026-08-25 ·Pierluigi San Pietro, Stefano Crespi Reghizzi, Antonio Restivo
publishedtheory similarity 0.54
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

Motivated by the study of closure operations on picture languages, we ask when a set of unary tiles can generate all sufficiently large pictures either via repeated horizontal and vertical concatenations or via tiling operations. In one dimension, the lengths of words in the concatenation closure of a unary language form an additive subsemigroup of positive natural numbers; hence, they are finitely generated. Cofiniteness is characterized by the gcd of these generators being one. Since ordinary cofiniteness in two dimensions is too restrictive and essentially reduces to degenerate one-dimensional conditions on strips, we introduce and study asymptotic cofiniteness: all sufficiently large rectangular pictures are generated. A direct extension of the one-dimensional criterion, requiring the gcd of the tile heights and of the tile widths to be one, is not sufficient, because local congruence obstructions may persist in two dimensions. We give an exact arithmetic characterization of asymptotic cofiniteness for arbitrary, possibly infinite, sets of unary rectangular tiles. The characterization is the same for the guillotine closure, obtained by horizontal and vertical concatenation, and for the full tiling closure. For finite tile sets, the proof combines semigroup arguments and an explicit least-common-multiple stacking construction for sufficiency, while necessity is obtained by a roots-of-unity argument applying also to nonsliceable tilings. The extension to infinite tile sets follows from the finite-basis theorem for Klarner systems.

0.36

A Strongly Aperiodic Monotile in Three Dimensions

cs.DM math.COmath.MG ·2026-09-16 ·Ioannis Tsiokos
theoryhighly cited similarity 0.53
Abstract

Socolar and Taylor asked for a single, simply connected three-dimensional prototile that forces nonperiodicity by shape alone, admitting no weakly nonperiodic tiling; the Schmitt-Conway-Danzer biprism and the three-dimensional Socolar-Taylor tile admit screw motions or a periodic stacking direction. We exhibit a rational polyhedral $3$-ball $Q$, which we call Chair44 (R44): a seven-cube chair whose $24$ exposed unit panels carry tiny square-pyramid features, and prove, as a proof submission, that $Q$ admits tilings of $\mathbb{R}^3$ by congruent copies, reflections allowed, and that every such tiling has no translational period and a symmetry group of order at most $24$; every tiling is homochiral and carries a unique infinite hierarchy of nested supertiles. The solid was designed to a reading of the aperiodic-monotile phenomenon reached with the Six Birds emergence calculus (Section 3.3), and the construction turns on a single finite test, checked by machine: the tile's own contact rule survives coarsening, so that the decoded parent tiling obeys the tile's rule and no other. The proof combines a written geometric argument, that the features force every tiling onto a registered lattice, with exhaustive finite enumerations; the companion census is replayed by two independent implementations, every finite gate is kernel-checked in Lean 4 (modulo a named compiler hook per native_decide theorem), and the written geometric lemmas and the logical assembly are Lean theorems as well, so that the theorem is kernel-checked modulo the named compiler hooks; the written proofs remain as exposition.

0.49

A new upper bound for Sidon sets in $\mathbb{F}_2^{4k+3}$

cs.IT math.CO ·2026-09-23 ·Darrion Thornburgh
theory similarity 0.53
Abstract · 7 pages

A subset $S \subseteq \mathbb{F}_2^n$ is called a Sidon set if no four distinct points of $S$ have zero sum. It is shown that if $n \geq 7$ and $n \equiv 3 \mod 4$, then $|S|\leq 2^{\frac{n+1}{2}}-3$. As a consequence, for any even $t \geq 4$, there does not exist a binary linear $[2^t-3,2^t-2t-2,5]$-code, strengthening a nonexistence result of Brouwer and Tolhuizen from 1993. As a second consequence, we also show that for an even integer $n \geq 4$, every almost perfect nonlinear (APN) function $F \colon \mathbb{F}_2^n \to \mathbb{F}_2^n$ has nonlinearity at least $3$.

0.21

Deterministic Constructions of Reed-Solomon Codes Beyond the Johnson Bound

cs.CC ·2026-10-22 ·Abhranil Chatterjee, Sumanta Ghosh, Zeyu Guo, Rohit Gurjar, Roshan Raj +1 more
similarity 0.52
Abstract

We give a deterministic quasipolynomial-time construction of Reed-Solomon codes that are list-decodable beyond the Johnson radius. Specifically, for every $ε\in(0,1]$ and all sufficiently large $n$, we construct an $[n,k]$ Reed-Solomon code of rate $R=Ω(ε/(1+\log(1/ε)))$ over a field of size $(nk)^{quasi-poly(nk)}$ that is $(1-ε,O(1/ε))$ list-decodable. The construction runs in quasi-poly(nk) time. We also give a deterministic construction of $[n,k]$-MDS$(3)$ Reed-Solomon codes for all integers $1\leq k<n$, with the same asymptotic bounds on field size and construction time. In the constant-rate regime, our field-size bound substantially improves the bound of $O(n^{k^{2k}})$ achieved by Roth's construction (Roth, IEEE TIT 2022). Our constructions exploit a connection to polynomial identity testing for read-once determinants, together with the quasipolynomial isolating-weight construction of Gurjar and Thierauf for linear matroid intersection (Gurjar and Thierauf, STOC 2017 and Computational Complexity 2020).

0.20