Evaluation of polynomials over finite rings via additive combinatorics (Q2075306)

Let us consider a finite ring \(R\) and denote by \(R^{(i)}\) an ideal that contains all the finite sums of terms \(\prod_{j=1}^i c_j \), such that \(c_1,\dots,c_i \in R\). If there is a positive \(i\in \mathbb{Z}\) such that \(R^{(i)}=0\) the ring is \textit{nilpotent} with \textit{nilpotency class} given by the minimal such \(i\). Let us now focus on two problems: \begin{itemize} \item \textit{Equivalence problem over a finite ring:} is it true that two polynomials define the same function over a given ring? \item \textit{Equation solvability problem:} is it true that two polynomials over some ring have at least one substitution, where they get the same value? It is related to the existence of a root or for the solution of an equation. \end{itemize} These problems originate from ring/field theory and they have been investigated in literature. The first problem has been proved to be decidable in polynomial time on a nilpotent ring and to be co-NP-complete in the other cases [\textit{S. Burris} and \textit{J. Lawrence}, J. Symb. Comput. 15, No. 1, 67--71 (1993; Zbl 0779.16007)]. Also the second problem is NP-complete for rings that are not nilpotent. In [\textit{G. Horváth}, Algebra Univers. 66, No. 4, 391--403 (2011; Zbl 1236.16046)] the author proves that for nilpotent rings the problem can be decided in polynomial time. If \(R\) is our nilpotent ring with size \(m\) and nilpotency class \(l\), let \(f\) a polynomial over \(R\) in \(n\) variables, we call \(\|f\|\) the number of operations that define it (that is also the complexity of evaluating it at a point in \(R^n\)). Now, according to [loc. cit.] the substitutions needed to decide whether \(f\) has a root or not is \(O(\|f\|^t)\), where \(t=t(m,l)\) comes from the Ramsey number of a specific colored hypergraph and is a big number. This paper reduces the exponent to \(m\log(m)\), via additive combinatorics' methods. In particular, the main theorem says Theorem. Let \(R\) be a nilpotent ring of size \(m\). For an \(n\)-variable polynomial \(f\in R[x_1,\dots,x_n]\), it can be decided in \(O(\|f\|n^{m\log(m)})\), time whether or not \(f\) has a root in \(R\).