Constructing Faithful Homomorphisms over Fields of Finite Characteristic

Authors Prerona Chatterjee , Ramprasad Saptharishi



PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2019.11.pdf
  • Filesize: 0.51 MB
  • 14 pages

Document Identifiers

Author Details

Prerona Chatterjee
  • Tata Institute of Fundamental Research, Mumbai, India
Ramprasad Saptharishi
  • Tata Institute of Fundamental Research, Mumbai, India

Cite AsGet BibTex

Prerona Chatterjee and Ramprasad Saptharishi. Constructing Faithful Homomorphisms over Fields of Finite Characteristic. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.FSTTCS.2019.11

Abstract

We study the question of algebraic rank or transcendence degree preserving homomorphisms over finite fields. This concept was first introduced by Beecken et al. [Malte Beecken et al., 2013] and exploited by them and Agrawal et al. [Manindra Agrawal et al., 2016] to design algebraic independence based identity tests using the Jacobian criterion over characteristic zero fields. An analogue of such constructions over finite characteristic fields were unknown due to the failure of the Jacobian criterion over finite characteristic fields. Building on a recent criterion of Pandey, Saxena and Sinhababu [Anurag Pandey et al., 2018], we construct explicit faithful maps for some natural classes of polynomials in fields of positive characteristic, when a certain parameter called the inseparable degree of the underlying polynomials is bounded (this parameter is always 1 in fields of characteristic zero). This presents the first generalisation of some of the results of Beecken, Mittmann and Saxena [Malte Beecken et al., 2013] and Agrawal, Saha, Saptharishi, Saxena [Manindra Agrawal et al., 2016] in the positive characteristic setting.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
  • Computing methodologies → Symbolic and algebraic manipulation
Keywords
  • Faithful Homomorphisms
  • Identity Testing
  • Algebraic Independence
  • Finite characteristic fields

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Manindra Agrawal and Somenath Biswas. Primality and identity testing via Chinese remaindering. J. ACM, 50(4):429-443, 2003. URL: https://doi.org/10.1145/792538.792540.
  2. Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, and Nitin Saxena. Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-D Occur-k Formulas and Depth-3 Transcendence Degree-k Circuits. SIAM J. Comput., 45(4):1533-1562, 2016. URL: https://doi.org/10.1137/130910725.
  3. Malte Beecken, Johannes Mittmann, and Nitin Saxena. Algebraic independence and blackbox identity testing. Information and Computing, 222:2-19, 2013. URL: https://doi.org/10.1016/j.ic.2012.10.004.
  4. Prerona Chatterjee and Ramprasad Saptharishi. Constructing Faithful Homomorphisms over Fields of Finite Characteristic. Electronic Colloquium on Computational Complexity (ECCC), 25:212, 2018. URL: https://eccc.weizmann.ac.il/report/2018/212.
  5. Richard A. DeMillo and Richard J. Lipton. A Probabilistic Remark on Algebraic Program Testing. Inf. Process. Lett., 7(4):193-195, 1978. URL: https://doi.org/10.1016/0020-0190(78)90067-4.
  6. Ariel Gabizon and Ran Raz. Deterministic extractors for affine sources over large fields. Combinatorica, 28(4):415-440, 2008. URL: https://doi.org/10.1007/s00493-008-2259-3.
  7. Zeyu Guo, Nitin Saxena, and Amit Sinhababu. Algebraic Dependencies and PSPACE Algorithms in Approximative Complexity. In Rocco A. Servedio, editor, 33rd Computational Complexity Conference, CCC 2018, June 22-24, 2018, San Diego, CA, USA, volume 102 of LIPIcs, pages 10:1-10:21. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.CCC.2018.10.
  8. C.G.J. Jacobi. De Determinantibus functionalibus. Journal für die reine und angewandte Mathematik, 22:319-359, 1841. URL: http://eudml.org/doc/147138.
  9. Neeraj Kayal. The Complexity of the Annihilating Polynomial. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pages 184-193, 2009. URL: https://doi.org/10.1109/CCC.2009.37.
  10. Adam R. Klivans and Daniel A. Spielman. Randomness efficient identity testing of multivariate polynomials. In Jeffrey Scott Vitter, Paul G. Spirakis, and Mihalis Yannakakis, editors, Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece, pages 216-223. ACM, 2001. URL: https://doi.org/10.1145/380752.380801.
  11. Mrinal Kumar and Shubhangi Saraf. Arithmetic Circuits with Locally Low Algebraic Rank. Theory of Computing, 13(1):1-33, 2017. URL: https://doi.org/10.4086/toc.2017.v013a006.
  12. Øystein Ore. Über höhere kongruenzen. Norsk Mat. Forenings Skrifter, 1(7):15, 1922. Google Scholar
  13. James G. Oxley. Matroid theory. Oxford University Press, 1992. Google Scholar
  14. Anurag Pandey, Nitin Saxena, and Amit Sinhababu. Algebraic independence over positive characteristic: New criterion and applications to locally low-algebraic-rank circuits. Computational Complexity, 27(4):617-670, 2018. URL: https://doi.org/10.1007/s00037-018-0167-5.
  15. Jacob T. Schwartz. Fast Probabilistic Algorithms for Verification of Polynomial Identities. J. ACM, 27(4):701-717, 1980. URL: https://doi.org/10.1145/322217.322225.
  16. Richard Zippel. Probabilistic algorithms for sparse polynomials. In Symbolic and Algebraic Computation, EUROSAM '79, An International Symposiumon Symbolic and Algebraic Computation, volume 72 of Lecture Notes in Computer Science, pages 216-226. Springer, 1979. URL: https://doi.org/10.1007/3-540-09519-5_73.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail