Evaluation of polynomials over finite rings via additive combinatorics

• Autores: Gyula Károlyi, Csaba Szabó
• Localización: Publicacions matematiques, ISSN 0214-1493, Vol. 66, Nº 1, 2022, págs. 197-205
• Idioma: inglés
• Enlaces
  • Texto completo
• Resumen

  • We give an improved polynomial bound on the complexity of the equation solvability problem, or more generally, of finding the value sets of polynomials over finite nilpotent rings. Our proof depends on a result in additive combinatorics, whichmay be of independent interest.

• Referencias bibliográficas
  • Zh. Alme˘ıda, M. V. Volkov, and S. V. Gol’dberg, Complexity of the identity checking problem for finite semigroups (Russian), Zap. Nauchn....
  • D. Brink, Chevalley’s theorem with restricted variables, Combinatorica 31(1) (2011), 127–130. DOI: 10.1007/s00493-011-2504-z.
  • S. Burris and J. Lawrence, The equivalence problem for finite rings, J. Symbolic Comput. 15(1) (1993), 67–71. DOI: 10.1006/jsco.1993.1004.
  • C. Chevalley, Démonstration d’une hypothèse de M. Artin, Abh. Math. Sem. Univ. Hamburg 11(1) (1935), 73–75. DOI: 10.1007/BF02940714.
  • A. Földvári , The complexity of the equation solvability problem over semipattern groups, Internat. J. Algebra Comput. 27(2) (2017), 259–272....
  • T. A. Gorazd and J. Krzaczkowski, Term equation satisfiability over finite algebras, Internat. J. Algebra Comput. 20(8) (2010), 1001–1020....
  • G. Horváth, The complexity of the equivalence and equation solvability problems over nilpotent rings and groups, Algebra Universalis 66(4)...
  • G. Horváth, The complexity of the equivalence and equation solvability problems over meta-Abelian groups, J. Algebra 433 (2015), 208–230....
  • G. Horvath and C. Szabó, The extended equivalence and equation solvability problems for groups, Discrete Math. Theor. Comput. Sci. 13(4) (2011),...
  • G. Horvath and C. Szabó, Equivalence and equation solvability problems for the alternating group A4, J. Pure Appl. Algebra 216(10) (2012),...
  • H. B. Hunt, III and R. E. Stearns, The complexity of equivalence for commutative rings, J. Symbolic Comput. 10(5) (1990), 411–436. DOI: 10.1016/...
  • O. Klíma, Complexity issues of checking identities in finite monoids, Semigroup Forum 79(3) (2009), 435–444. DOI: 10.1007/s00233-009-9180-y.
  • J. E. Olson, A combinatorial problem on finite Abelian groups, I, J. Number Theory 1 (1969), 8–10. DOI: 10.1016/0022-314X(69)90021-3.
  • S. H. Schanuel, An extension of Chevalley’s theorem to congruences modulo prime powers, J. Number Theory 6(4) (1974), 284–290. DOI: 10.1016/0022-314X...
  • S. Seif and C. Szabó, Computational complexity of checking identities in 0-simple semigroups and matrix semigroups over finite fields, Semigroup...
  • P. Tesson and D. Thérien, Monoids and computations, International Conference on Semigroups and Groups in honor of the 65th birthday of Prof....