CS Paper Radar

Exact curve counting of given word length on the once-punctured torus

Filippo Baroni, David Fisac, Mingkun Liu

cs.CG math.GTmath.CO ·submitted 2026-09-01 15:15 UTC · v1
unusual

Abstract

On the once-punctured torus, we give an exact formula for the number of curves in any given mapping class group orbit of given word length. This settles a conjecture of Chas in [Cha16].

Comment
25 pages, 8 figures

Closest papers

Nearest neighbours by meaning across the whole index.

$k$-arrangements of pseudolines and pseudocircles

cs.CG math.CO ·2026-09-30 ·Jan Kynčl, Carolina Medina, Gelasio Salazar
theory similarity 0.52
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

Simple symmetric Venn diagrams with 17, 19 and 23 curves

cs.CG math.COcs.DM ·2026-09-22 ·Chris Dzoba
code/dataunusual similarity 0.49
Abstract · 15 pages, 2 figures. Certificates, independent checker, Lean 4 verifications and search code are archived at doi:10.5281/zenodo.22885649 and…

We exhibit simple, rotationally symmetric Venn diagrams with 17 curves, with 19 curves and with 23 curves: $n$ Jordan curves carried to one another by rotation through $2π/n$, with every one of the $2^n$ regions present and connected and, since the diagrams are simple, every crossing on exactly two curves. Symmetric Venn diagrams exist for every prime number of curves (Griggs, Killian and Savage, 2004), but those diagrams have many curves through a point; simple ones were known only up to 13 curves (Mamakani and Ruskey, 2014). Four 17-curve, twelve 19-curve and six 23-curve diagrams were found by a Metropolis walk on rotation-invariant quadrangulations of the sphere in which regions may temporarily be duplicated, started from the Griggs-Killian-Savage diagram with its multiple crossings resolved. At 23 curves the walk was held for two weeks by duplicated regions near the poles; the two lineages that finished were the first whose $E=92$ states had none. Every diagram is given by a machine-checkable certificate; one certificate each of the 17-, 19- and 23-curve sizes has been verified by a formal proof in Lean 4. All of the diagrams are non-monotone, which is why the crossing-sequence searches that found the 11- and 13-curve diagrams could not have found them.

0.45

Lengths and Counting of Palindromic Prefixes of Standard Sturmian Words

cs.FL math.CO ·2026-11-15 ·Jasem Hamoud
similarity 0.49
Abstract

Every standard Sturmian word $c_\mathbf{d}$ is determined by a directive sequence $\mathbf{d}=(d_i)_{i\ge 1}$ of positive integers, and its palindromic prefixes are obtained by iterated palindromic closure. We describe the lengths of these prefixes by the numbers $j\,\ell_{i-1}+\ell_{i-2}-2$, where $\ell_n$ is the length of the $n$-th standard word and $1\le j\le d_i$, and we show that each nonzero length is attained by exactly one pair $(i,j)\neq(1,1)$. For a purely periodic directive sequence of period $k$ we then prove that the number $π_\mathbf{d}(N)$ of nonempty palindromic prefixes of length at most $N$ satisfies \[ π_\mathbf{d}(N)\sim\frac{d_1+\cdots+d_k}{\logλ_\mathbf{d}}\,\log N, \] where $λ_\mathbf{d}$ is the largest eigenvalue of the matrix $M(d_1)\cdots M(d_k)$. For the Fibonacci word this gives $π_\mathbf{d}(N)\sim\log N/\log\varphi$, where $\varphi=(1+\sqrt5)/2$.

0.30

Length Bounds for MDS Algebraic Geometry Codes of Arbitrary Positive Genus

cs.IT ·2026-10-29 ·Haojie Chen, Chuangqiang Hu, Guorui Ma
theory similarity 0.48
Abstract

We study the length of maximum distance separable algebraic geometry codes from curves of arbitrary positive genus. For fixed genus, we prove that the asymptotic ratio of the length to the field size is at most $1/2$ when both the dimension and the codimension grow faster than the logarithm of the field size. We also give explicit bounds under logarithmic dimension conditions. The bounds hold in every characteristic and are uniform in the curve and the evaluation set. The proof combines character sums on the Jacobian with an estimate for sums of distinct points.

0.43

Word Length and Diameter in Permutation Groups

cs.CC math.GR ·2026-09-22 ·Markus Lohrey, Alexander Thumm
similarity 0.47
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

Shorthand Universal Tori for Permutations: Existence, Symmetry, and Generation of Twori

cs.DM math.CO ·2026-09-23 ·Tim Gerlach, Elizabeth Hartung, Pia Herkenrath, Joe Sawada, Aaron Williams
similarity 0.46
Abstract

A de Bruijn sequence packs all $n$-bit binary words into a cycle of length $2^n$. A de Bruijn torus is the two-dimensional analogue in which each word appears exactly once in a rectangular window. Here we consider the natural analogue for permutations using their shorthand representation (i.e., each permutation's final redundant value is omitted from the window). We show that these tori exist when $n = 2m + 1$ is odd and the torus and windows have two rows (i.e., the torus is a "tworus"). These twori can be constructed with a high degree of symmetry. More specifically, there are twori that can be partitioned into $2^{m-1}$ matching blocks where each block contains the same sequence of unordered columns. Furthermore, given one such block we can generate each successive column of a tworus in amortized $\mathcal{O}(1)$-time. We also prove non-existence results for certain sizes of tori and provide algorithms for constructing multiversal cycles (perfect necklaces) of unlabeled binary words.

0.23

Smallest String Attractors and Minimal Coverage Certificates of Thue--Morse Words

cs.DS math.COcs.FL ·2026-10-07 ·Simone Faro, Francesco Pio Marino, Arianna Pavone
theory similarity 0.46
Abstract

String attractors provide a compact way of representing the complete factor structure of a word: a set of positions is an attractor if every distinct factor has at least one occurrence crossing one of the selected positions. Although the minimum attractor size is known for several classical families of words, describing \emph{all} optimal attractors is typically much more difficult, since it requires understanding the geometry of all factor occurrences rather than constructing a single optimal solution. We give a complete description for the finite Thue--Morse words. Earlier work proved that four positions are necessary and sufficient for every order $n\geq 4$, but the collection of all smallest attractors remained unknown. For every $n\geq 6$, writing $h=2^{n-3}$, we prove that the smallest attractors are exactly the two reflected families where the four offsets are chosen independently from $\{0,1\}$. Hence there are exactly $32$ smallest attractors for every $n\geq6$. The initial cases are genuinely exceptional: $t_5$ has $40$ smallest attractors and $t_4$ has $87$. We also study the attractor condition independently of optimality. For every $n\geq5$, we characterize the complete antichain of inclusion-minimal factor coverages of $t_n$. It consists precisely of the coverages of $aa$, $bb$, and the eight minimal unique substrings of every generation $t_m$, $4\leq m\leq n$. Thus there are exactly $8n-22$ canonical constraints, forming an irredundant exact certificate for attractors of arbitrary cardinality. When attention is restricted to four-position sets, this linear-size system collapses to a constant one: it is enough to test the $24$ minimal unique substrings coming from three consecutive generations, and sixteen of these already force the two optimal families. We also show that three generations are necessary within this natural consecutive-generation hierarchy.

0.51

Some results on Archdeacon's conjecture for rotation systems

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