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 language | English (US) |
---|---|
Pages (from-to) | 15-21 |
Number of pages | 7 |
Journal | Discrete Mathematics |
Volume | 173 |
Issue number | 1-3 |
DOIs | |
State | Published - Aug 20 1997 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics