CS Paper Radar

Up or down at every integer: Collatz-type maps of arbitrary sets and the up-down graph

Oleg Vasilyev

cs.DM math.DSmath.NT ·submitted 2026-11-16 00:13 UTC · v2

Abstract

For a set $S$ of positive integers let $T_S$ send $x$ to $\lceil 3x/2\rceil$ if $x\in S$ and to $\lceil x/2\rceil$ otherwise. The odd numbers give the Collatz map, the even numbers give it again after a shift by one, and $S=\mathbb{N}$ gives Mahler's map $x\mapsto\lceil 3x/2\rceil$. All these maps are subgraphs of the up-down graph $G$, in which every $x$ has the edges $x\to\lceil x/2\rceil$ and $x\to\lceil 3x/2\rceil$, and so are the families of maps in which the direction is forced at some numbers and free at the others. The cycles of the maps are the simple cycles of the subgraph, their divergent orbits are its rays, and all maps of a family are bounded exactly when the subgraph has no ray. We classify the simplest sets and show that density says little: some sets of density one send every orbit to 1, and some periodic sets of arbitrarily small density have increasing orbits. Every positive integer is the least element of a cycle of some map. The critical proportion of steps up is $\log_3 2$: cycles stay below it, divergent orbits stay above it, and both come arbitrarily close. For sets periodic modulo a power of 2, an effective up-frequency from a finite Markov chain takes the place of the density, and a finite computation can prove that every orbit reaches a cycle. Mahler's Z-number problem is implied by a question about one such map. Finally, we ask how far the Collatz map is from maps whose behaviour can be proved. Finite changes never help. Adding fewer than $\log_{3/2}N+1$ even numbers below $N$ makes an orbit increase, while removing the odd numbers congruent to 9 or 15 modulo 16, an eighth of all integers, gives a map all of whose orbits provably reach the cycle (1,2); removing 22 residue classes modulo 512, a proportion 0.043, also suffices.

Closest papers

Nearest neighbours by meaning across the whole index.

Up or down by half: a family of Collatz-type maps

cs.DM math.DS ·2026-11-06 ·Oleg Vasilyev
theoryunusual similarity 0.57
Abstract

Each Collatz step changes a positive integer by roughly half: odd inputs go up and even inputs go down. We vary the directions while keeping the step size. Write x=2^m k (k odd), and let S be a set of positive integers. Define T_S(x)=(3x+1)/2 if m=0, 3x/2 if m is in S, and k otherwise. The map T_S^- differs only at odd x, which it sends to (x+1)/2. The usual Collatz map is T_emptyset. Assuming the independence of 2-adic valuations along odd-to-odd steps yields random-walk models with drifts (1+rho(S))log_2(3)-2 for T_S and rho(S)log_2(3)-2 for T_S^-, where rho(S) is an explicit series. Every T_S^- is contracting; T_S is contracting exactly when rho(S)<log_3(4/3), approximately 0.2619. We prove density results, classify interval sets S, and give a criterion ensuring every T_S^- orbit reaches 1 or (2,3). For seven contracting maps T_S, three with rho(S)=1/4 just below the threshold, computations show that every n<2^34 (n<1.668*10^10 for S={1}) reaches one of at most five cycles; stopping-time statistics match the model to 3-5 digits. We study branching maps, where any member of a family may be applied at each step. Boundedness of a family implies boundedness of each member; in particular, boundedness of {T_emptyset,T_{3}} would imply that no Collatz orbit diverges. For {T_emptyset,T_{1}}, a rule depending only on x mod 32 has positive drift (10/17)log_2(9/8) for almost every 2-adic starting point. Thus almost all n have reachable sets containing values larger than n^1.05; residues modulo 2^L, L<=10, cannot prove unboundedness. Finally, we define unified maps in which valuations also determine the direction at odd inputs. The cases x=1 mod 4 govern their behavior: if they go down, every block is dominated by the corresponding Collatz map (and a census finds only the cycles (1), (2, 3) and (3, 5) with smallest element below 10^9); if they go up, the maps behave like T_S.

0.49

Spectral Stability, Fatou Basin Contraction, and Machine-Checked Multipliers in Holomorphic Extensions of Generalized Syracuse Dynamics

cs.LO cs.SCmath.CVmath.DS ·2026-11-08 ·Volkan Dağlı, Zerrin Dağlı, Dağhan Dağlı, Emrah Yurtseven, Murat Emre Özkaya
theoryunusual similarity 0.52
Abstract · 3 pages, 3 tables; includes ancillary Lean 4 formalization (anc/CollatzAttractor.lean, 20 machine-checked theorems, 0 sorry) and Python veri…

We embed the Syracuse operator $T(n) = n/2$ (even $n$), $T(n) = (3n+1)/2$ (odd $n$) and the Collatz map $C(n)$ into $\mathbb{C}$ via entire functions of exponential type $π$: $f(z) = \frac{1}{4}(1 + 4z - (1 + 2z)\cos(πz))$ and $F(z) = \frac{1}{4}(2 + 7z - (2 + 5z)\cos(πz))$. We prove five results: (1) every integer periodic cycle $C \subset \mathbb{N}^+$ of $T$ is a strictly attracting Fatou cycle of $f$ with multiplier $μ_f(C) = 3^{N_{\mathrm{odd}}}/2^N = \prod_{n \in C\text{ odd}} \frac{3n}{3n+1} \in (0,1)$, and $μ_f(O_{1,2}) = μ_F(O_{1,4,2}) = 3/4 < 1$; (2) on the Fatou basin $B(O_{1,2})$, $g = f^{\circ 2}$ conjugates to $Φ_j(g(z)) = \frac{3}{4}Φ_j(z)$ with Koenigs Taylor jets $c_2(1) = -\frac{13}{2}π^2$ and $d_2(2) = -\frac{9}{2}π^2$; (3) the Schwarzian derivative is strictly negative on $\mathbb{Z}$ ($S(f)(n) \le 3π^2 - \frac{3}{8}π^4 \approx -6.9196 < 0$), and a repelling Julia 2-cycle $O_{\mathrm{rep}} \subset J(f)$ ($μ\approx 1.2148 > 1$) isolates $B(O_{1,2})$; (4) on $(\mathbb{Z}_2, μ_{\mathrm{Haar}})$, the 2-adic Lyapunov exponent $λ_{\mathrm{Haar}} = \frac{1}{2}\ln(3/4) \approx -0.143841 < 0$ equals $\frac{1}{2}\ln|μ_f(O_{1,2})|$; and (5) we certify 20 theorems in Lean 4 (anc/CollatzAttractor.lean, 0 sorry). These results establish local Fatou invariants and 2-adic ergodic averages for $f(z)$, leaving open whether every $n_0 \in \mathbb{N}^+$ lies in $\bigcup_{k \ge 0} f^{-k}(B(O_{1,2}))$.

0.37

Some results on Archdeacon's conjecture for rotation systems

cs.CG math.CO ·2026-09-10 ·Arahat Chikkatur, Ji Zeng
theory similarity 0.50
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

An Improved Bound for Smith's Longest Cycles Conjecture via a Forbidden Subdivision

cs.DM math.CO ·2026-08-31 ·Douglas M. Chen
hot direction similarity 0.49
Abstract · 9 pages, 2 figures. Comments welcome!

Smith's conjecture asserts that in every $k$-connected graph with $k\geq 2$, any two longest cycles intersect in at least $k$ vertices. In this work, we establish an $Ω(k^{8/11})$ bound for this conjecture, improving upon the $Ω(k^{2/3})$ bound of Ma and Zhao. Our proof combines a Ramsey theoretic refinement of the traditional Turán-type approach with computer search.

0.50

Distinguishing graphs with simple spectrum by homomorphism counts

cs.DM math.CO ·2026-10-06 ·Takanori Maehara
theory similarity 0.49
Abstract · 32 pages, 8 figures

We study which graph classes determine every graph with simple spectrum up to isomorphism by homomorphism counts from their members. We show that such a class has unbounded treewidth and Euler genus and contains a graph with the complete graph on seven vertices as a minor. To prove these conditions, we construct pairs of non-isomorphic cospectral graphs with simple spectrum, each bipartite, nonsingular and of maximum degree at most six. The construction attaches rooted trees to Cai-Furer-Immerman graphs and preserves homomorphism indistinguishability over every minor-closed class. We then prove that subcubic homomorphism counts determine every graph whose adjacency matrix has kernel dimension at most one. This extends the known result for nonsingular graphs and applies to all graphs with simple spectrum. We also prove that two graphs have the same subcubic homomorphism counts if and only if they have the same number of vertices and there is a bijective linear isometry between the images of their adjacency matrices that intertwines the adjacency operators and preserves the coordinatewise trilinear forms. Finally, we prove that homomorphism counts from the single-vertex graph and from subdivisions of any sequence of connected cubic graphs have the same distinguishing power as subcubic homomorphism counts if every complete graph is a minor of some member of the sequence.

0.27

Flip-packability: uniform characterisations of tame graph classes

cs.LO cs.DMmath.COmath.LO ·2026-09-27 ·Ioannis Eleftheriadis
theory similarity 0.49
Abstract · 32 pages; added funding information

A class of graphs is monadically dependent if one cannot encode all graphs in coloured graphs from the class using a fixed first-order formula, and monadically stable if one cannot even encode arbitrarily long linear orders. Bonnet et al. (ICALP 2025) characterised monadic dependence by flip-separability: for every vertex weighting, boundedly many flips - complementations of the adjacency relation within a vertex subset - make every ball of radius $r$ carry at most an $\varepsilon$-fraction of the weight, so that every set carrying an $\varepsilon$-fraction has two elements pulled apart. We introduce flip-packability: boundedly many graphs, each obtained from the input by boundedly many flips and all determined by the weighting before any set is presented, such that every set carrying an $\varepsilon$-fraction of the weight has $m$ elements pairwise far apart in one of them. The number of flips producing each graph depends on the radius alone; only the number of graphs depends on $\varepsilon$ and $m$. We prove that a class of graphs is flip-packable if and only if it is monadically stable, and $2$-flip-packable, that is, flip-packable with $m=2$, if and only if it is monadically dependent. The passage from two scattered elements to $m$ is thus exactly what separates the two notions. For monadically stable classes we show that the flipped graphs can be computed from the weighting in cubic time. Varying the three parameters of the definition - the sparsifying operation, the radius, and the number $m$ of elements scattered - produces eight known characterisations of sparse and dense graph classes from the same template. In each case $m$ separates a depth-like notion from its width-like relaxation: treedepth from treewidth, shrubdepth from cliquewidth, and monadic stability from monadic dependence.

0.24

Counterexamples to the Strong Roberson Conjecture

cs.DM math.COcs.LO ·2026-10-02 ·Arnar Á. Kristjánsson
similarity 0.49
Abstract · 24 pages. v2: expanded introduction, related work and conclusion; improved exposition throughout; smaller explicit counterexamples obtained

We refute the Strong Roberson Conjecture, which asserts that adding any graph outside a graph class closed under minors and disjoint unions strictly increases the distinguishing power of homomorphism counts from that class. More precisely, we construct connected graphs $H$ for which homomorphism counts from graphs excluding $H$ as a minor determine the number of homomorphisms from $H$ to any target graph. We also refute the analogous conjecture with immersions in place of minors. The proof introduces a method for deriving exact homomorphism count dependence from modular equivalences. We obtain these modular equivalences for infinitely many primes using prime-order automorphisms and the corresponding orbit quotients. We complete the refutations by proving that suitable circulant graphs with two jump lengths and related cubic bipartite graphs exclude their corresponding orbit quotients as minors and immersions, respectively.

0.45

Additive cubes are avoidable over $\{0,1,2,3\}$, $\{0,1,4\}$ and $\{0,2,5\}$

cs.DM math.COcs.FL ·2026-11-13 ·Damien Jamet, Matthieu Rosenfeld
theory similarity 0.48
Abstract

We prove that additive cubes are avoidable over the alphabet $\{0,1,2,3\}$, thereby solving a long-standing question initiated by Pirillo and Varricchio in 1994. By extending the reduction and spectral machinery of Cassaigne, Currie, Schaeffer, and Shallit (2014), we prove that the search for additive cubes in such morphic images reduces to a finite graph traversal. We exhibit eight explicit morphisms from $\{0,1,3,4\}^*$ to $\{0,1,2,3\}^*$ of length 3 whose images on the Cassaigne \textit{et al.} infinite word contain no additive cubes.

0.24