On reducing a system of equations to a single equation

ABSTRACT

For a system of polynomial equations over Q;_p; we present an efficient construction of a single polynomial of quite small degree whose zero set over Q;_p; coincides with the zero set over Q;_p; of the original system. We also show that the polynomial has some other attractive features such as low additive and straight-line complexity.The proof is based on a link established here between the above problem and some recent number theoretic result about zeros of p-adic forms.

REFERENCES

• 1: Y. Alemu, 'On zeros of forms over local fields', Acta Arithm., 45 (1985), 163--171.
• 2: G. I. Arkhipov and A. A. Karatsuba, 'On a problem in the theory of congruences', Uspechi Mat. Nauk, 37 (1981), 161--162 (in Russian).
• 3: G. I. Arkhipov and A. A. Karatsuba, 'On the local representation of zero by a form', Izv. Akad Nauk USSR, 19 (1982), 231--240 (in Russian).
• 4: Michael Ben-Or, A deterministic algorithm for sparse multivariate polynomial interpolation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.301-309, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62241]
• 5: J. Browkin, 'On systems of congruences', Bull. of the Polish Acad. Sci., 31 (1983), 219--226.
• 6: J. Brownawell, 'On p-adic zeros of forms', J. Number Theory, 18 (1984), 342--349.
• 7: P. Burgisser, M. Clausen and M. A. Shokrollahi, Algebraic complexity theory, Springer-Verlag, Berlin, 1996.
• 8: Jonathan F. Buss , Gudmund S. Frandsen , Jeffery O. Shallit, The computational complexity of some problems of linear algebra, Journal of Computer and System Sciences, v.58 n.3, p.572-596, June 1999 [doi>10.1006/jcss.1998.1608]
• 9: Michael Clausen , Andreas Dress , Johannes Grabmeier , Marek Karpinski, On zero-testing and interpolation of k -sparse multivariate polynomials over finite fields, Theoretical Computer Science, v.84 n.2, p.151-164, July 29, 1991 [doi>10.1016/0304-3975(91)90157-W]
• 10: D. Grigoriev, 'Lower bounds in the algebraic computational complexity', Zapiski Nauchn. Semin. Leningr. Otdel. Matem. Inst. Acad. Sci. USSR, 118 (1982), 25--82 (in Russian).
• 11: Dima Yu. Grigoriev , Marek Karpinski, Algorithms for sparse rational interpolation, Proceedings of the 1991 international symposium on Symbolic and algebraic computation, p.7-13, July 15-17, 1991, Bonn, West Germany [doi>10.1145/120694.120696]
• 12: Dima Grigoriev , Marek Karpinski, A Zero-Test and an Interpolation Algorithm for the Shifted Sparse Polynominals, Proceedings of the 10th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.162-169, May 10-14, 1993
• 13: Dima Yu Grigoriev , Marek Karpinski , Michael F. Singer, Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields, SIAM Journal on Computing, v.19 n.6, p.1059-1063, Dec. 1990 [doi>10.1137/0219073]
• 14: Dima Grigoriev , Marek Karpinski , Michael F. Singer, Computational Complexity of Sparse Rational Interpolation, SIAM Journal on Computing, v.23 n.1, p.1-12, Feb. 1994 [doi>10.1137/S0097539791194069]
• 15: Marek Karpinski , Alf van der Poorten , Igor Shparlinski, Zero testing of p-adic and modular polynomials, Theoretical Computer Science, v.233 n.1-2, p.309-317, Feb. 28 2000 [doi>10.1016/S0304-3975(99)00133-4]
• 16: Marek Karpinski , Igor Shparlinski, On some approximation problems concerning sparse polynomials over finite fields, Theoretical Computer Science, v.157 n.2, p.259-266, May 5, 1996 [doi>10.1016/0304-3975(95)00162-X]
• 17: A. G. Khovanski, Fewnomials, Amer. Math. Soc., Providence, 1991.
• 18: D. J. Lewis and H. L. Montgomery, 'On zeros of p-adic forms', Michigan Math. J., 30 (1983), 83--87.
• 19: Li L. Lipshitz, 'P-adic zeros of polynomials', J. Reine Angew. Math., 390 (1988), 208--214.
• 20: Richard Lipton , Nisheeth Vishnoi, Deterministic identity testing for multivariate polynomials, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 21: J.-J. Risler, 'Khovansky's theorem and complexity theory', Rocky Mountain J. Math., 14 (1984), 851--853.
• 22: J.-J. Risler, 'Additive complexity of real polynomials', SIAM J. Comp., 14 (1985), 178--183.
• 23: J. Maurice Rojas, Additive Complexity and Roots of Polynomials over Number Fields and \mathfrak{p} -adic Fields, Proceedings of the 5th International Symposium on Algorithmic Number Theory, p.506-516, July 07-12, 2002
• 24: J. M. Rojas, 'Arithmetic multivariate Descartes' rule', Amer. J. Math., 126 (2004) 1--30.
• 25: Ron M. Roth , Gyora M. Benedek, Interpolation and approximation of sparse multivariate polynomials over GF(2), SIAM Journal on Computing, v.20 n.2, p.291-314, April 1990 [doi>10.1137/0220019]
• 26: W. M. Schmidt, 'The solubility of certain p-adic equations', J. Number Theory, 19 (1984), 63--80.
• 27: Igor E. Shparlinski, Sparse polynomial approximation in finite fields, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.209-215, July 2001, Hersonissos, Greece [doi>10.1145/380752.380803]
• 28: K. Werther, 'The complexity of sparse polynomials interpolation over finite fields', Appl. Algebra in Engin., Commun. and Comp., 5(1994), 91--103.
• 29: R. Zippel, Effective polynomial computation, Kluwer Acad. Publ., Dordrecht, 1993.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.m Miscellaneous

General Terms:
Theory

Keywords:
system of equations