CS Paper Radar

Construction and formal verification of a special topology on {\mathbb{Z}}^{n}: characterization of connected subsets

Ignacio Vega-Páez

cs.SC cs.LO ·submitted 2026-10-29 04:47 UTC · v1
theory

Abstract

We examine whether the integers admit a topology whose connected subsets are precisely the sets of consecutive integers. The main result gives a construction for every integer lattice {\mathbb{Z}}^{n}, n>0; the answer for Z is then obtained as a corollary. We prove that the neighborhoods determined by the parity of the sum of the coordinates form a basis and that topological connectedness agrees exactly with accessibility by finite paths of unit lattice steps. We also present a deductive audit and the correspondence between this argument and a verification in Lean 4 and Mathlib, including the empty set and the independent formal characterization of integer intervals. The construction and mathematical result originate in Problem 5712, proposed by Dan Marcus and solved in 1970 by the Cleveland State University group; the present article contributes a detailed exposition and a report on formal verification.

Closest papers

Nearest neighbours by meaning across the whole index.

UTVPI-representable integer point sets: discrete convexity, polymorphisms, and pairwise closure

cs.DM ·2026-08-25 ·Kei Kimura, Kazuhisa Makino, Shota Yamada, Ryo Yoshizumi
theory similarity 0.54
Abstract · 48 pages, v2: acknowledgments updated, references added

We study subsets of the integer lattice represented by single-variable-per-inequality (SVPI), difference-constraint (DC), unit two-variable-per-inequality (UTVPI), and two-variable-per-inequality (TVPI) systems. We relate five viewpoints: inequality representation, discrete convexity, polymorphisms, reconstruction from two-coordinate projections, and fixed points of closure operators. Our central result completely characterizes UTVPI-representability. For every set $S\subseteq\mathbb Z^n$ with $n>1$, \[ \begin{aligned} &S\text{ is UTVPI-representable}\\ &\;\Longleftrightarrow\; S\text{ is closed under the directed midpoint and median operations}\\ &\;\Longleftrightarrow\; S\text{ is integrally convex and $2$-decomposable}. \end{aligned} \] The median condition may instead be replaced by closedness under some majority operation, and the same class is the fixed-point class of a pairwise directed-midpoint closure operator. Thus, all five viewpoints yield equivalent characterizations of UTVPI-representability. In particular, $2$-decomposability is exactly the global condition needed to lift the known two-dimensional equivalence between integral convexity and UTVPI-representability to arbitrary dimension. This theorem is embedded in a broader pairwise-closure theory. For a family $F$ of operations, we define a closure operator by closing every two-coordinate projection under $F$ and joining the resulting sets. Its fixed points are precisely the sets that are both $2$-decomposable and $F$-closed, and we establish a local-to-global criterion for such characterizations. A closed-convex-hull analogue characterizes TVPI-representability. We also characterize SVPI-representability by natural multioperations, prove limitations of operation-based characterizations for several related classes, and determine the complete inclusion hierarchies in the general, Boolean, and two-dimensional settings.

0.26

Global Trace Condition for Injective Transition Graphs

cs.LO ·2026-11-03 ·Stefano Berardi, Ugo de'Liguoro, Daniel Osorio-Valencia
theoryhot direction similarity 0.48
Abstract

We formulate the global trace condition, GTC, for cyclic proofs as a particular case of the size-change termination condition, or SCT. We express cyclic proofs through a variant of size-change graphs, called transition graphs, whose edges are labelled by (finite) bipartite relations. We show that injective transition graphs suffice to encode cyclic pre-proofs for a variant of Brotherston and Simpson's sequent calculus with inductive definitions. The injectivity of transition graphs corresponds to restricting SCT to fan-in-free graphs. Then we prove that an essentially weaker condition implies SCT in this case, and hence GTC.

0.33

Discrete Temporal CSPs et al

cs.CC math.LO ·2026-10-15 ·Lukas Pieper
similarity 0.48
Abstract

We revisit the complexity classification of constraint satisfaction problems (CSPs) for first-order reducts of $(\mathbb{Z},<)$, established by Bodirsky, Martin, and Mottet in 2018. Following their approach, we give a self-contained proof of this classification, correcting several errors in the argument. We further show that, with the exception of cases arising from finite-domain CSPs, all tractable cases are solved by a well-known uniform algorithm, eliminating the need for the collection of ad-hoc algorithms used in the original paper. A central component of the proof allows the analysis to be restricted to first-order reducts of $(\mathbb{Z},<)$ that contain the successor relation. We substantially simplify this reduction and generalize the underlying construction. This generalization allows us to apply the same technique to first-order reducts of the triangular lattice graph and of infinite regular trees, yielding a complete complexity classification for these classes of structures, in particular a $\mathsf{P}$ versus $\mathsf{NP}$-complete dichotomy.

0.21

Spectrum of the refined Diophantine exponent

cs.FL math.COmath.DSmath.NT ·2026-08-20 ·Quang-Khai Nguyen
similarity 0.47
Abstract · Reorganize the paper, fix the argument in Section 5, remove and add some questions

The refined Diophantine exponent, recently introduced by the author, is a quantity that measures the periodicity of an infinite word. In this article, we study this exponent from combinatorial and topological viewpoints. First, we show that, over a ternary alphabet, the spectrum of the refined Diophantine exponent is $[1,\infty]$. Second, we show that this exponent has topological properties similar to those of the set of Liouville numbers. Finally, we provide concrete examples with the Champernowne, Rudin--Shapiro, and Thue--Morse words, words coming from coding a rotation by intervals, and bracket words.

0.25

On the Complexity of Locally Dense Lattices

cs.CC ·2026-08-15 ·Shuichi Hirahara, Kazuki Ogitsuka
published similarity 0.47
Abstract · Full version of MFCS 2026

\emph{Locally dense lattices} are central gadgets used to prove the hardness of the Shortest Vector Problem and related lattice problems. Informally, a locally dense lattice is a lattice $\mathcal{L}$ that contains exponentially many lattice vectors inside some $\ell_p$ ball centered at $\vec{s}$ with radius at most an $α< 1$ fraction of the length of its shortest nonzero lattice vector. In this paper, taking a ``meta'' viewpoint on locally dense lattices, we introduce the \emph{Locally Dense Lattice Problem} (LDLP), the decision problem of determining whether a given input specifies a locally dense lattice. Our main result is that LDLP in $\ell_p$ norms for all finite $p \geq \log_2 3$ and for the infinity norm is complete for the second level of the polynomial hierarchy. We also compare two standard definitions of local density that appear in prior work. Micciancio's original definition (FOCS 1998 and SICOMP 2001) uses integer coefficient vectors, while later work by Micciancio (ToC 2012) and by Bennett and Peikert (RANDOM 2023) uses short vectors in a shifted coset. We show that the corresponding promise problems are mutually reducible in deterministic polynomial time, which shows that the two formulations are robust.

0.52

On the Existence of Complete Coverings of Lee Spheres

cs.IT ·2026-10-26 ·Jing Zhang, Yue Zhou
theory similarity 0.46
Abstract

Every perfect $r$-error-correcting Lee code in $\mathbb{Z}^n$ induces a finite configuration around each codeword: a family of pairwise disjoint radius-$r$ Lee spheres, all disjoint from the central sphere, that covers every lattice point at Lee distance $r+1$ from the codeword. We call such a configuration a complete covering. Under projection onto a suitable Cartesian product of cycles, a complete covering corresponds to an optimal local structure in the sense of Špacapan. The existence of a complete covering is necessary but, in general, not sufficient for the existence of a perfect Lee code, as our construction for $(n,r)=(3,2)$ shows. We prove that no complete covering exists whenever $n\ge 8$ and $r^2+\lfloor 25r/34\rfloor-3\ge 2n$. For the corresponding Cartesian products of cycles, this strengthens Špacapan's nonexistence theorem by replacing the linear radius condition $r\ge n$ with a threshold of order $\sqrt{2n}$. We also obtain an improved large-radius nonexistence bound for perfect Lee codes, strengthening the bound of Horak and Kim. Furthermore, we show that, for every $\varepsilon>0$, no complete covering exists when $n\ge 3$, $r$ is sufficiently large, and $r^2+(2/\mathrm{e}-\varepsilon)r\ge 2n$. On the positive side, we use near-optimal ternary constant-weight codes to construct almost complete coverings whose pairwise disjoint shadows cover a $1-o(1)$ proportion of the first outer Lee shell as the dimension tends to infinity, for every fixed radius.

0.11

Comments on "Multidimensional Costas Arrays and Their Periodicity"

cs.IT math.CO ·2026-10-25 ·Shiv Munagala
similarity 0.46
Abstract · Comment arXiv:2208.02378

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.

0.27

A note on Finiteness and Boundedness in Cartesian Products of Discrete and Well-Ordered Sets, Application to Transition Systems

cs.DM cs.FL ·2026-10-12 ·Gerard Memmi
theoryunusual similarity 0.46
Abstract · 15 pages 0 figure

In this short note, we prove that any closed interval in a well-ordered and discrete space is finite. The coincidence between finiteness and boundedness can then be established for transition systems where the state space is well-ordered and discrete. Finally, this result is also proven when the state space is a Cartesian product of $d$ discrete and well-ordered sets.

0.29