Congruence preservation and polynomial functions from ℤn to ℤm

Research output: Contribution to journalArticle

8 Scopus citations

Abstract

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
Volume173
Issue number1-3
DOIs
StatePublished - Aug 20 1997
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

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

  • Cite this