On pseudo-polynomials.

*(English)*Zbl 0226.10019The 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.

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 |