An Algorithmic Characterization Of Polynomial Functions Over Zpn
Abstract
The problem of polynomial representability of functions is central to many branches of mathematics. If the underlying set is a finite field, every function can be represented as a polynomial. In this thesis we consider polynomial representability over a special class of finite rings, namely, Zpn, where p is a prime and n is a positive integer. This problem has been studied in literature and the two notable results were given by Carlitz(1965) and Kempner(1921).While the Kempner’s method enumerates the set of distinct polynomial functions, Carlitz provides a necessary and sufficient condition for a function to be polynomial using Taylor series. Further, these results are existential in nature.
The aim of this thesis is to provide an algorithmic characterization, given a prime p and a positive integer n, to determine whether a given function over Zpn is polynomially representable or not. Note that one can give an exhaustive search algorithm using the previous results. Our characterization involves describing the set of polynomial functions over Zpn with a ‘suitable’ generating set. We make use of this result to give an nonexhaustive algorithm to determine whether a given function over Zpn is polynomial representable.nβ
Collections
Related items
Showing items related by title, author, creator and subject.

Exploring Polynomial Convexity Of Certain Classes Of Sets
Gorai, Sushil (20110718)Let K be a compact subset of Cn . The polynomially convex hull of K is defined as The compact set K is said to be polynomially convex if = K. A closed subset is said to be locally polynomially convex at if there ... 
Grobuer Basis Algorithms for Polynomial Ideal Theory over Noetherian Commutative Rings
Francis, Maria (20180514)One of the fundamental problems in commutative algebra and algebraic geometry is to understand the nature of the solution space of a system of multivariate polynomial equations over a field k, such as real or complex ... 
Towards a Charcterization of the Symmetries of the NisanWigderson Polynomial Family
Gupta, Nikhil (20180709)Understanding the structure and complexity of a polynomial family is a fundamental problem of arithmetic circuit complexity. There are various approaches like studying the lower bounds, which deals with nding the smallest ...