CS Paper Radar

Bluebirds and mockingbirds cannot produce a fixed-point combinator

Takuma Imamura

cs.LO math.LO ·submitted 2026-09-18 13:35 UTC · v3
unusual

Abstract

Let $B$ be the bluebird combinator with reduction rule $Bxyz \to_{w} x\left(yz\right)$, let $M$ be the mockingbird combinator with reduction rule $Mx \to_{w} xx$, and let $I$ be the identity bird combinator with reduction rule $Ix \to_{w} x$. A fixed-point combinator, called a sage bird by Smullyan, is a closed term $Y$ such that, for a fresh variable $x$, $Yx$ is equivalent to $x\left(Yx\right)$ under these reduction rules. For a fixed variable $x$, we construct an invariant $\mathrm{Tr}_{x}\left(u\right)$ of a $BMI$-term $u$ with respect to $\to_{w}$. This invariant traces the occurrences of $x$ in the leftmost-innermost reduction sequence of $u$. We then prove that $\mathrm{Tr}_{x}\left(Yx\right) \neq \mathrm{Tr}_{x}\left(x^{r}\left( Yx \right)\right)$ for every $x$-free $BMI$-term $Y$ and every $r\geq 1$. Consequently, there exists no fixed-point combinator in $BMI$-combinatory logic. This provides a negative answer to the problem posed by Smullyan in 1985.

Comment
Revised

Closest papers

Nearest neighbours by meaning across the whole index.

Finite $\mathbf{BM}$-algebras and fixed-point combinators

cs.LO math.LO ·2026-10-27 ·Takuma Imamura
theory similarity 0.61
Abstract

We study algebras for the $\mathbf{BM}$-, $\mathbf{BI}$-, and $\mathbf{BMI}$-fragments of combinatory logic, where $\mathbf{B} xyz \to_{w} x\left(yz\right)$, $\mathbf{M} x \to_{w} xx$ and $\mathbf{I} x \to_{w} x$. We prove that every finite $\mathbf{BM}$-algebra $\mathcal{A}$ contains an element $Y$ satisfying $Yx = x\left(Yx\right)$ for all $x\in A$. Moreover, a single closed $\mathbf{BM}$-term represents such an element in every finite $\mathbf{BM}$-algebra. On the other hand, we show that there exists an infinite $\mathbf{BMI}$-algebra with no such element. Consequently, the variety of $\mathbf{BM}$-algebras is not generated by finite $\mathbf{BM}$-algebras. We also characterise finite $\mathbf{BI}$-algebras as finite semigroups with two distinguished left units $B$ and $I$, and finite $\mathbf{BMI}$-algebras as finite idempotent semigroups with three distinguished left units $B$, $M$ and $I$.

0.25

Three Conjectures on Binary Channels for the Doubly Symmetric Binary Source

cs.IT ·2026-09-23 ·Georg Pichler
theorycode/datahot direction similarity 0.45
Abstract

We settle three conjectures concerning a doubly symmetric binary source $(X,Y)$ with crossover $p$. Consider Markov chains $U - X - Y - V$ with $U,V$ binary, and let $\mathcal{A}$ be the set of rate triples $(I(U;V),I(U;X),I(Y;V))$ attainable with arbitrary binary channels $X\to U$, $Y\to V$, and $\mathcal{B}$ the subset attainable with binary symmetric channels. The averaged BSC conjecture, Conjecture 5.2 of Pichler, Piantanida and Matz (2022), asserts $\operatorname{conv}\mathcal{A}=\operatorname{conv}\mathcal{B}$. We prove this for every $p\in[0,1]$. Two conjectures of Dikshtein, Ordentlich and Shamai (2022) concern the double-sided information bottleneck at $p=0$, where $Y=X$ and the two channels see the same source: their Conjecture 1 identifies the exact maximum of $I(U;V)$ at prescribed rates $I(U;X)$ and $I(Y;V)$, and their Conjecture 2 the exact minimum. We prove both for binary $U,V$: the two extrema are attained by the same pair of Z/S-channels, in opposite orientation for the maximum and in the same orientation for the minimum. The proofs were found with substantial AI assistance, and all three theorems are formalised in Lean 4 with Mathlib, depending only on the standard axioms. The development is available at https://github.com/g-pichler/bsc-averaging . The proof of Conjecture 1 of Dikshtein, Ordentlich and Shamai (2022) contains three certified computations, a polynomial bound, an interval sweep and a polynomial positivity certificate, all of which are checked in Lean.

0.58

Computing distances in braid-move graphs, higher Bruhat orders, and oriented-matroid mutation graphs is NP-hard

cs.DM math.CO ·2026-10-01 ·Tilen Marc
theorycode/data similarity 0.44
Abstract · 33 pages, 5 figures. v2: restructured and several proofs shortened. Code, computational checks and Lean formalization: https://github.com/ti…

A wiring diagram is an arrangement of $m$ pseudolines, every two of which cross exactly once. Reading its crossings from left to right encodes it as a reduced word of the permutation $w_0\in S_m$ that reverses $1,\dots,m$, unique up to commutations, and a braid move $σ_iσ_{i+1}σ_i\leftrightarrowσ_{i+1}σ_iσ_{i+1}$ flips one of its triangles. We prove that deciding whether two wiring diagrams are within a given braid-move distance is NP-complete. Equivalently, deciding flip distance is NP-complete in the higher Bruhat order $B(m,2)$, for triangle flips of marked arrangements of pseudolines, and for rhombic tilings of a $2m$-gon; this answers an open question on flip graphs of pseudoline arrangements (SODA 2024). The reduction is from Vertex Cover: for every graph $G$ we construct two wiring diagrams at braid-move distance $|D|+2\operatorname{VC}(G)$, where $\operatorname{VC}(G)$ is the vertex cover number of $G$ and the Hamming distance $|D|$ is the number of triples of wires whose triangles are oriented differently. The construction glues copies of a seven-wire gadget whose braid-move distance exceeds its Hamming distance by $2$. Adding a line at infinity transfers the construction to rank-$3$ uniform oriented matroids, where two oriented matroids are adjacent in the mutation graph if their chirotopes differ in one basis; so deciding distance in the mutation graph is NP-complete in rank $3$. An iterate of Rambau's expansion of signotopes amplifies the excess and gives NP-hardness in every fixed rank $r\ge4$, and by duality in every fixed corank at least $3$. The same instances show that flip distance in the higher Bruhat orders $B(n,k)$ is NP-complete for every fixed $k\ge2$.

0.46

A Compact Weight-Space Integer Programming Formulation for Balanced Minimum Evolution

cs.DM ·2026-10-08 ·Leonid Chindelevitch, Matthew Penn, Samir Bhatt
benchmark similarity 0.43
Abstract · 44 pages, 1 figure

Balanced Minimum Evolution (BME) reconstructs an unrooted binary phylogenetic tree from a distance matrix $D$ by minimizing the length $\sum_{i<j}D_{ij}w_{ij}$, which is linear in the weights $w_{ij}=2^{-d_T{ij}}$. We study the formulation of BME in these $\binom{n}{2}$ weight variables. Theoretical results. (i) For a fixed topology $T$, the Kraft equalities, the cut equalities $\{W[S]=\tfrac12\}$ of $T$, and the single convex constraint $\sum w_{ij} \log_2 w_{ij} \leq \tfrac{3}{2}-n$ admit exactly one point, the tree's weight vector. (ii) For every tree and every bipartition, the cut value $W_T[S]$ lies in $\{\tfrac{1}{2}\} \cup \{\tfrac{3}{4}\} \cup [\tfrac{7}{8}, \infty)$; the value $\tfrac{3}{4}$ is attained exactly by the $2(n-3)$ bipartitions created by one nearest-neighbour interchange; and the number of bipartitions with $W_T[S]\le1$ is $2n^2-10n+15$ for every binary topology. (iii) The crossing graph of nontrivial bipartitions has an edge clique cover with $O(n^4)$ cliques, and every edge clique cover needs $Ω(n^2)$. (iv) The necessary conditions of Catanzaro et al. for a path-length matrix, without the four-point condition, are sufficient for $n \leq 11$ and first fail at $n=12$. Computational results. A compact branch-and-bound solver built on these results, which commits and forbids splits and imposes the convex constraint exactly, certifies optimality on benchmark instances with up to $n=20$ taxa within an hour. It is faster than the distance-indexed model of Catanzaro et al. on two of these instances and slower on the others; that model, whose root bound is tighter, certifies 13 of 14 benchmark instances with $n \leq 30$ within an hour in every seed. Although the compact solver does not improve on the computational state of the art overall, we explain why, and we discuss the open problems that our results raise.

0.30

Proof of the Kahn Saks Conjecture

cs.DM math.CO ·2026-09-25 ·Max Aires
theory similarity 0.42
Abstract · 25 pages

Let $\mathbb{P}(x\prec y)$ be the probability that $x$ precedes $y$ in a uniformly random linear extension of an $n$-element poset $P$, and define the balancing coefficient to be $δ(x,y)=\min(\mathbb{P}(x\prec y),\mathbb{P}(y\prec x))$ with $δ(P)=\max_{x,y}δ(x,y)$. We prove (Theorem 1) that sufficiently large width forces $δ(P)$ to be arbitrarily close to $1/2$, answering a long-standing conjecture of Kahn and Saks. In fact, we prove the stronger result (Theorem 2) that large width forces one of two configurations in our poset: either a nearly uniform order on $k$ vertices, or an almost fixed order on $t$ vertices with one further vertex inserted uniformly among the $t+1$ slots. We also show that, for fixed $k$, the first possibility must occur within any antichain $X$ of size $Ω(n^{2/3})$.

0.49

Rényi stability of $B_h$ sets: a two-order phase diagram and sharp deletion principles

cs.IT math.CO ·2026-09-20 ·Jae Oh Woo
theory similarity 0.41
Abstract · 29 pages, 1 figure

A set $B$ in an abelian group is a $B_h$ set if every $h$-term sum has a unique representation up to permutation; for $h=2$ these are the Sidon sets. We study a weighted removal problem for this collision-free property: if the $h$-fold sum map has small Rényi entropy loss, how much probability mass must be deleted so that the remaining support is a $B_h$ set? Two Rényi orders arise: $α$ is the order at which the coarsening loss is measured, whereas $β$ is the order of the entropy constraint. The diagonal specialization $β=α$ ties the two roles together. We determine the resulting stability problem on the positive $(α,β)$-quadrant. Stability holds exactly when $β\le1$ and $α\geβ$. Inside this region the optimal deletion rate is polynomial for $β<1$ and logarithmic on the boundary $β=1$, where the leading constant is exact; outside it, stability fails through two distinct mechanisms: a supercritical budget and dilution by light atoms. In both unstable regimes the limiting defect is computed exactly. The upper bounds follow from a coarsening inequality with best possible constant, which also yields an entropy-free removal theorem, a finite combinatorial consequence for moments of the representation function, and extensions to $B_h[g]$ sets. Matching constructions show that the phase boundaries and rates are sharp.

0.29

Prefix-Tuning for Arbitrary Output Sequences on Pretrained Transformers

cs.CL cs.AIcs.LG ·2026-10-16 ·Peter Cho-Ho Lam, Ziyi Wang, Zirui Zhou
top venuetheorycode/dataunusual similarity 0.41
Abstract · Accepted at NeurIPS 2026. Code: https://github.com/wzii/prefix_tuning. Online demo: https://wzii.github.io/prefix_tuning/

Prefix-tuning is a parameter-efficient fine-tuning method for large language models (LLMs) that steers model outputs by prepending task-specific prefix representations to the input sequence. Despite its practical success, the theoretical understanding of the expressiveness of prefixes remains incomplete. In particular, the following question remains open: Given a pretrained autoregressive Transformer, for any input-output sequence pair $(\mathtt{x},\mathtt{y})$, does there always exist a prefix $\mathcal{S}$ such that prepending $\mathcal{S}$ to $\mathtt{x}$ induces the model to generate the target output $\mathtt{y}$? In this work, we prove that under the assumption that $\mathtt{y}$ is in the range of the pretrained Transformer, such a prefix $\mathcal{S}$ exists and can be explicitly computed by solving multiple linear systems. We further show that this assumption is necessary, in the sense that such a prefix may not exist when the assumption fails, thereby providing a complete answer to the above question. Our analysis is constructive and the obtained theoretical results hold under fairly general assumptions on model architecture. Extensive experiments on GPT-2 and Qwen3-4B demonstrate that our algorithm produces prefixes with strong control over model outputs.

0.48

A combinatorial proof of a symmetric joint distribution on strict binary trees

cs.DM math.CO ·2026-11-18 ·Shishuo Fu
similarity 0.41
Abstract · 11 pages, 2 figures

Nonplanar strict binary trees on $2n+1$ vertices are enumerated by the reduced tangent numbers $T_{2n+1}/2^n$, whose entries are refined by Poupard's triangle. Poupard defined the end of the minimal chain ($\mathrm{eoc}$) and the parent of the maximum leaf ($\mathrm{pom}$) on these trees, proving that $\mathrm{eoc}$ and $\mathrm{pom}+1$ share this triangular distribution. Foata and Han subsequently showed via tree calculus and partial difference equations that the joint distribution of $(\mathrm{eoc}, 2n+1-\mathrm{pom})$ is symmetric. By introducing an auxiliary tree statistic dual to $\mathrm{eoc}$, we give a bijective proof of this symmetry. Our proof composes a recursive bijection on strict binary trees, a bijection to alternating André permutations, and the reverse-complement involution on permutations.

0.42