Arithmetical Complexity and Absoluteness of Rigidity Phenomena for Ulam Sequences

Abstract

We analyse the arithmetical complexity and forcing absoluteness of natural statements about Ulam sequences. For positive integers $a<b$, membership in $U(a,b)$ and the increasing enumeration of $U(a,b)$ are uniformly primitive recursive. We encode the finite interval-with-periodic-mask descriptions used in rigidity results and formalise the finite-window rigidity theorem for the family $U(1,n)$: for every prescribed linear window, one finite collection of residue-class-dependent pattern data works for all sufficiently large parameters $n$. This family statement has a ${\Pi }_3^0$ upper bound in the arithmetical hierarchy; for a fixed window its complexity is ${\Sigma }_2^0$. For an individual $U(a,b)$, eventual periodicity of the gap sequence (with positive period) and finiteness of specified residue classes are ${\Sigma }_2^0$, while rational upper-density, lower-density, and exact-density assertions have ${\Pi }_3^0$ upper bounds. These are classifications by upper bounds, not completeness claims. Since the resulting sentences are arithmetical, their truth is unchanged by set forcing. This semantic forcing invariance is distinguished from proof-theoretic conservativity over stronger set theories. Finally, if the gaps of $U(a,b)$ are eventually periodic with positive period, then $U(a,b)$ is Presburger-definable; hence $(\mathbb{N},+,{\mathrm{U}}_{a,b})$ is decidable, NIP, dp-minimal, and does not interpret full arithmetic.

Major correction. The earlier fixed-pair rigidity formulation and several associated complexity and absoluteness claims have been corrected. The replacement uses the published varying-parameter finite-window rigidity schema, retains the Pi^0_3 family and Sigma^0_2 fixed-window upper bounds, and removes unsupported completeness, reverse-mathematical, and model-theoretic overclaims