TY - JOUR

T1 - Congruence preservation and polynomial functions from ℤn to ℤm

AU - Bhargava, Manjul

N1 - Funding Information:
This work was done during the 1995 Research Experience for Undergraduates at the University of Minnesota, Duluth, directed by Joseph Gallian and sponsored by the National Science Foundation (grant number DMS-9225045) and the National Security Agency (grant number MDA 904-91-H-0036).

PY - 1997/8/20

Y1 - 1997/8/20

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0010892668&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0010892668&partnerID=8YFLogxK

U2 - 10.1016/S0012-365X(96)00093-3

DO - 10.1016/S0012-365X(96)00093-3

M3 - Article

AN - SCOPUS:0010892668

VL - 173

SP - 15

EP - 21

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 1-3

ER -