Non-interpretability of multiplication for Ulam expansions

Let (a,b)(a,b) be coprime, and let Ua,b\mathcal{U}_{a,b} denote the expansion of (N,+,0,1)(\mathbb{N},+,0,1) by the predicate for the associated Ulam sequence. Non-interpretability of multiplication. For every coprime (a,b)(a,b), the expansion Ua,b\mathcal{U}_{a,b} does not interpret (N,+,×)(\mathbb{N},+,\times). That is, there is no formula φ(x,y,z)\varphi(x,y,z) in the language {0,1,+,Ua,b}\{0,1,+,\mathrm{U}_{a,b}\} defining the graph of multiplication on an infinite domain. The conjecture is motivated by the purely additive character of the Ulam construction and the absence of an apparent mechanism for encoding multiplicative relations; 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.