Ulam dichotomy for expansions of Presburger arithmetic
Ulam dichotomy for expansions of Presburger arithmetic
Let be coprime, and let be the expansion of by the predicate for the associated Ulam sequence. Ulam dichotomy. For every coprime , exactly one of the following holds:
- The expansion is a reduct of a definitional expansion of Presburger arithmetic, possibly with countably many parameters, and in particular is NIP, dp-minimal, and does not interpret .
- The expansion interprets , and in particular has the independence property and is model-theoretically wild.
Moreover, case 2 does not occur: every Ulam expansion falls into case 1. This conjecture proposes a dichotomy between Presburger-like tameness and interpretation of full arithmetic, while asserting that only the tame case occurs; its status is open.
Sources & referencesView supporting material
Primary source
Frank Gilson, “Arithmetical Complexity and Absoluteness of Rigidity Phenomena for Ulam Sequences”, arXiv:2511.13066 (2025).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.