We analyse the logical complexity and absoluteness of natural statements about Ulam sequences, with particular emphasis on the rigidity phenomena introduced by Hinman, Kuca, Schlesinger and Sheydvasser for the family $U(1,n)$. For each pair of coprime integers $a<b$ we view the associated Ulam sequence $U(a,b)$ as a recursive subset of $\mathbb{ N}$ and consider expansions of the form $(\mathbb{ N},+,\mathrm{ U}_{ a,b})$. Our first main result is a uniform coding of Ulam sequences and of the ``interval with periodic mask'' patterns appearing in rigidity conjectures into first-order arithmetic. Using this, we show that the strong rigidity, regularity (eventual periodicity of gaps), and density statements for $U(a,b)$ are all arithmetical and lie at low levels of the arithmetical hierarchy (e.g.\ $\Sigma^0_2$ or $\Pi^0_3$). As a consequence, these statements are absolute between transitive models of $\mathrm{ ZFC}$ with the same natural numbers: their truth value cannot be changed by forcing, and is independent of the Continuum Hypothesis and large cardinal axioms. We also study the expansions $(\mathbb{ N},+,\mathrm{ U}_{ a,b})$ model-theoretically, showing that combinatorial rigidity implies tameness properties (NIP, dp-minimality, non-interpretability of multiplcation).
Categories: math.LO