[math-fun] Chebyshev/Dickson representation of polynomials
The really cool Chebfun computer algebra system represents polynomials in a Chebyshev basis instead of a "monomial" (power) basis: www.chebfun.org Among other things, there are "fast" algorithms for computing products of polys in a Chebyshev basis. The recent discussions of "permutation polynomials" led to finding that some of these polynomials are *Dickson* polynomials -- i.e., Chebyshev polynomials! Soooo, inspired by Chebfun, perhaps polynomials over finite fields should also be represented by Chebyshev/Dickson polynomials. Such a representation inverts the discussion, because we are now representing (at least in some cases) non-permutation polynomials in terms of permutation polynomials. Perhaps someone has already done this?
From my bib file. You may want to start with Lidl. Can send files if hard to get (personal email).
%\bibitem{}{James Alexander, Paul Hearding: %\jjbibtitle{A graph theoretic encoding of Lucas sequences}, %arXiv:1501.00061 [math.CO], \bdate{31-December-2014}, %URL: \url{http://arxiv.org/abs/1501.00061}.} %% comb. interpretation of Dickson polynomials %\bibitem{}{Bijan Ansari, M.\ Anwar Hasan: %\jjbibtitle{Revisiting Finite Field Multiplication Using Dickson Bases}, % CACR 2007-06, \bdate{2007}. %URL: \url{http://www.cacr.math.uwaterloo.ca/}.} %\bibitem{}{Cunsheng Ding: %\jjbibtitle{Cyclic Codes from Dickson Polynomials}, %arXiv:1206.4370v1 [cs.IT], \bdate{20-June-2012}. %URL: \url{http://arxiv.org/abs/1206.4370}.} %\bibitem{}{Robert W.\ Fitzgerald, Joseph L.\ Yucas: %\jjbibtitle{Generalized reciprocals, factors of Dickson polynomials and generalized cyclotomic polynomials over finite fields}, %Finite Fields and Their Applications, vol.~13, no.~3, pp.~492-515, \bdate{July-2007}. %URL: \url{http://dx.doi.org/10.1016/j.ffa.2006.03.002}.} %\bibitem{}{Robert W.\ Fitzgerald, Joseph L.\ Yucas: %\jjbibtitle{Explicit Factorizations of Cyclotomic and Dickson Polynomials over Finite Fields}, %Lecture Notes in Computer Science, vol.~4547, Springer-Verlag, \bdate{2007}. %URL: \url{}.} %\bibitem{}{Joachim von zur Gathen, Jos\'{e} Luis Imana, \c{C}etin Kaya Ko\c{c} (eds.): %\jjbibtitle{Arithmetic of finite fields}, %second international workshop, WAIFI 2008, Siena, Italy, % Lecture Notes in Computer Science, vol.~5130, \bdate{2008}. %\bibitem{}{M.\ Anwar Hasan, Christophe Negre: %\jjbibtitle{Subquadratic space complexity multiplication over binary fields with Dickson polynomial representation}, %Lecture Notes in Computer Science, vol.~5130, WAIFI 2008, Springer-Verlag, \bdate{2008}.} %% ***** SUGGEST TO LOOK AT THIS ONE FIRST: ***** %\bibitem{}{Rudolf Lidl, G.\ L.\ Mullen, G.\ Turnwald: %\jjbibtitle{Dickson Polynomials}, %Longman, \bdate{1993}. %% ***** SUGGEST TO LOOK AT THIS ONE AS WELL: ***** \bibitem{Intr2FF}{Rudolf Lidl, Harald Niederreiter: \jjbibtitle{Introduction to finite fields and their applications}, Cambridge University Press, revised edition, \bdate{1994}.} %\bibitem{}{Rudolf Lidl, Gary L.\ Mullen: %\jjbibtitle{When does a polynomial over a finite field permute the elements of the field?}, %The American Mathematical Monthly, vol.~95, no.~3, pp.~243-246, \bdate{March-1988}. %%: IRRED %\bibitem{}{Rudolf Lidl, Gary L.\ Mullen: %\jjbibtitle{When does a polynomial over a finite field permute the elements of the field?, II}, %The American Mathematical Monthly, vol.~100, no.~1, pp.~71-74, \bdate{January-1993}. %\bibitem{dicksonbases}{Ronald C.\ Mullin, Ayan Mahalanobis: %\jjbibtitle{Dickson Bases and Finite Fields}, %URL: \url{http://www.cacr.math.uwaterloo.ca/techreports/2005/cacr2005-03.pdf}. %\bibitem{dicksonnormal}{Alfred Scheerhorn: %\jjbibtitle{Dickson Polynomials, Completely Normal Polynomials and the Cyclic Module Structure of Specific Extensions of Finite Fields}, %Designs, Codes and Cryptography, vol.~9, pp.~193-202, \bdate{1996}.} %\bibitem{}{Thomas Stoll: %\jjbibtitle{Complete decomposition of Dickson-type recursive polynomials and related Diophantine equations}, %J. Number Theory, vol.~128, 1157-1181, \bdate{2008}. %URL: \url{http://iecl.univ-lorraine.fr/~Thomas.Stoll/publ.html}.} * Henry Baker <hbaker1@pipeline.com> [Mar 24. 2016 12:29]:
The really cool Chebfun computer algebra system represents polynomials in a Chebyshev basis instead of a "monomial" (power) basis:
www.chebfun.org
Among other things, there are "fast" algorithms for computing products of polys in a Chebyshev basis.
The recent discussions of "permutation polynomials" led to finding that some of these polynomials are *Dickson* polynomials -- i.e., Chebyshev polynomials!
Soooo, inspired by Chebfun, perhaps polynomials over finite fields should also be represented by Chebyshev/Dickson polynomials.
Such a representation inverts the discussion, because we are now representing (at least in some cases) non-permutation polynomials in terms of permutation polynomials.
Perhaps someone has already done this?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Thanks, Joerg! This is a terrific set of links on this subject. At 12:57 AM 3/26/2016, Joerg Arndt wrote:
From my bib file. You may want to start with Lidl. Can send files if hard to get (personal email).
%\bibitem{}{James Alexander, Paul Hearding: %\jjbibtitle{A graph theoretic encoding of Lucas sequences}, %arXiv:1501.00061 [math.CO], \bdate{31-December-2014}, %URL: \url{http://arxiv.org/abs/1501.00061}.} %% comb. interpretation of Dickson polynomials
%\bibitem{}{Bijan Ansari, M.\ Anwar Hasan: %\jjbibtitle{Revisiting Finite Field Multiplication Using Dickson Bases}, % CACR 2007-06, \bdate{2007}. %URL: \url{http://www.cacr.math.uwaterloo.ca/}.}
%\bibitem{}{Cunsheng Ding: %\jjbibtitle{Cyclic Codes from Dickson Polynomials}, %arXiv:1206.4370v1 [cs.IT], \bdate{20-June-2012}. %URL: \url{http://arxiv.org/abs/1206.4370}.}
%\bibitem{}{Robert W.\ Fitzgerald, Joseph L.\ Yucas: %\jjbibtitle{Generalized reciprocals, factors of Dickson polynomials and generalized cyclotomic polynomials over finite fields}, %Finite Fields and Their Applications, vol.~13, no.~3, pp.~492-515, \bdate{July-2007}. %URL: \url{http://dx.doi.org/10.1016/j.ffa.2006.03.002}.}
%\bibitem{}{Robert W.\ Fitzgerald, Joseph L.\ Yucas: %\jjbibtitle{Explicit Factorizations of Cyclotomic and Dickson Polynomials over Finite Fields}, %Lecture Notes in Computer Science, vol.~4547, Springer-Verlag, \bdate{2007}. %URL: \url{}.}
%\bibitem{}{Joachim von zur Gathen, Jos\'{e} Luis Imana, \c{C}etin Kaya Ko\c{c} (eds.): %\jjbibtitle{Arithmetic of finite fields}, %second international workshop, WAIFI 2008, Siena, Italy, % Lecture Notes in Computer Science, vol.~5130, \bdate{2008}.
%\bibitem{}{M.\ Anwar Hasan, Christophe Negre: %\jjbibtitle{Subquadratic space complexity multiplication over binary fields with Dickson polynomial representation}, %Lecture Notes in Computer Science, vol.~5130, WAIFI 2008, Springer-Verlag, \bdate{2008}.}
%% ***** SUGGEST TO LOOK AT THIS ONE FIRST: ***** %\bibitem{}{Rudolf Lidl, G.\ L.\ Mullen, G.\ Turnwald: %\jjbibtitle{Dickson Polynomials}, %Longman, \bdate{1993}.
%% ***** SUGGEST TO LOOK AT THIS ONE AS WELL: ***** \bibitem{Intr2FF}{Rudolf Lidl, Harald Niederreiter: \jjbibtitle{Introduction to finite fields and their applications}, Cambridge University Press, revised edition, \bdate{1994}.}
%\bibitem{}{Rudolf Lidl, Gary L.\ Mullen: %\jjbibtitle{When does a polynomial over a finite field permute the elements of the field?}, %The American Mathematical Monthly, vol.~95, no.~3, pp.~243-246, \bdate{March-1988}.
%%: IRRED %\bibitem{}{Rudolf Lidl, Gary L.\ Mullen: %\jjbibtitle{When does a polynomial over a finite field permute the elements of the field?, II}, %The American Mathematical Monthly, vol.~100, no.~1, pp.~71-74, \bdate{January-1993}.
%\bibitem{dicksonbases}{Ronald C.\ Mullin, Ayan Mahalanobis: %\jjbibtitle{Dickson Bases and Finite Fields}, %URL: \url{http://www.cacr.math.uwaterloo.ca/techreports/2005/cacr2005-03.pdf}.
%\bibitem{dicksonnormal}{Alfred Scheerhorn: %\jjbibtitle{Dickson Polynomials, Completely Normal Polynomials and the Cyclic Module Structure of Specific Extensions of Finite Fields}, %Designs, Codes and Cryptography, vol.~9, pp.~193-202, \bdate{1996}.}
%\bibitem{}{Thomas Stoll: %\jjbibtitle{Complete decomposition of Dickson-type recursive polynomials and related Diophantine equations}, %J. Number Theory, vol.~128, 1157-1181, \bdate{2008}. %URL: \url{http://iecl.univ-lorraine.fr/~Thomas.Stoll/publ.html}.}
* Henry Baker <hbaker1@pipeline.com> [Mar 24. 2016 12:29]:
The really cool Chebfun computer algebra system represents polynomials in a Chebyshev basis instead of a "monomial" (power) basis:
www.chebfun.org
Among other things, there are "fast" algorithms for computing products of polys in a Chebyshev basis.
The recent discussions of "permutation polynomials" led to finding that some of these polynomials are *Dickson* polynomials -- i.e., Chebyshev polynomials!
Soooo, inspired by Chebfun, perhaps polynomials over finite fields should also be represented by Chebyshev/Dickson polynomials.
Such a representation inverts the discussion, because we are now representing (at least in some cases) non-permutation polynomials in terms of permutation polynomials.
Perhaps someone has already done this?
participants (2)
-
Henry Baker -
Joerg Arndt