# zbMATH — the first resource for mathematics

On pseudo-polynomials. (English) Zbl 0226.10019
The author defines a pseudo-polynomial to be a function $$f: \mathbb Z^+\cup\{0\}\to \mathbb Z$$ such that $$f(n+k) \equiv f(n)\pmod k$$ for all integers $$n\geq 0$$, $$k\geq 1$$. I am grateful to Professor Sanford L. Segal for pointing out to me that these functions appear earlier in the literature as “universal functions” in a paper by N. G. de Bruijn [Nederl. Akad. Wet., Proc. Ser. A 58, 363–367 (1955; Zbl 0067.27301)]. The present paper contains three theorems, the first of which is also given by de Bruijn.
Theorem 1. $$f(x)$$ is a pseudo-polynomial if and only if
$f(x) =A_0 +A_1x + (A_2/2!)x(x-1) + (A_3/3!)x(x-1)(x-2) + \ldots$
where every $$A_n$$ is an integer and is divisible by $$\lcm [1,2,3,\ldots,m]$$.
Theorem 2. The ring of pseudo-polynomials, denoted by $$P[x]$$, is an integral domain but not a unique factorization domain.
Theorem 3. If $$f(x)$$ is a pseudo-polynomial and $$| f(x)| = O(\theta^x)$$ for some $$\theta<e-1$$, then $$f(x)$$ is a polynomial.
It has been conjectured by I. Ruzsa that a pseudo-polynomial is either a polynomial or increases as fast as $$e^n$$, but this seems difficult and has not been proved. The paper contains the example $$[n!e]$$ of a pseudo-polynomial in closed form.
Reviewer: R. R. Hall

##### MSC:
 11A25 Arithmetic functions; related numbers; inversion formulas 11C08 Polynomials in number theory 11B83 Special sequences and polynomials 13G05 Integral domains 13F99 Arithmetic rings and other special commutative rings
##### Keywords:
universal integer-valued functions
Full Text: