Ulam dichotomy for expansions of Presburger arithmetic

Let (a,b)(a,b) be coprime, and let Ua,b\mathcal{U}_{a,b} be the expansion of (N,+,0,1)(\mathbb{N},+,0,1) by the predicate for the associated Ulam sequence. Ulam dichotomy. For every coprime (a,b)(a,b), exactly one of the following holds:

  1. The expansion Ua,b\mathcal{U}_{a,b} 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 (N,+,×)(\mathbb{N},+,\times).
  2. The expansion Ua,b\mathcal{U}_{a,b} interprets (N,+,×)(\mathbb{N},+,\times), 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.