We study the extension of Presburger arithmetic by the class of sub-polynomial Hardy field functions, and show the majority of these extensions to be undecidable. More precisely, we show that the theory Th(ℤ; < , +, ⌊f⌉), where f is a Hardy field function and ⌊⋅⌉ the nearest integer operator, is undecidable when f grows polynomially faster than x. Further, we show that when f grows sub-linearly quickly, but still as fast as some polynomial, the theory Th(ℤ; < , +, ⌊f⌉) is undecidable.
Brown et al. (Thu,) studied this question.