Congruence preservation and polynomial functions from ℤn to ℤm

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


A function f: ℤn → ℤm is said to be congruence preserving if for all d dividing m and a,b ∈ {0, 1,...,n - 1}, a ≡ b (mod d) implies f(a) = f(b) (mod d). In previous work, Chen defines the notion of a polynomial function from ℤn to ℤm and shows that any such function must also be a congruence preserving function. Chen then raises the question as to when the converse is true, i.e. for what pairs (n,m) is a congruence preserving function f : ℤn → ℤm necessarily a polynomial function? In the present paper, we give a complete answer to Chen's question by determining all such pairs. We also show that 7/π2 is the natural density in ℕ of the set of all m such that the polynomial functions from ℤm to itself are precisely the congruence preserving functions from ℤm to itself. Moreover, we obtain a formula for the number of congruence preserving functions from ℤn to ℤm.

Original languageEnglish (US)
Pages (from-to)15-21
Number of pages7
JournalDiscrete Mathematics
Issue number1-3
StatePublished - Aug 20 1997
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Congruence preservation and polynomial functions from ℤn to ℤm'. Together they form a unique fingerprint.

Cite this