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

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
Full Text: DOI