Return to search

An Algorithmic Characterization Of Polynomial Functions Over Zpn

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 non-exhaustive algorithm to determine whether a given function over Zpn is polynomial representable.nβ

Identiferoai:union.ndltd.org:IISc/oai:etd.ncsi.iisc.ernet.in:2005/2337
Date02 1900
CreatorsGuha, Ashwin
ContributorsDukkipati, Ambedkar
Source SetsIndia Institute of Science
Languageen_US
Detected LanguageEnglish
TypeThesis
RelationG25316

Page generated in 0.0016 seconds