Graph colourings and solutions of systems of equations over finite fields

A congruence f(x1,x2,…,xt)≡0modpn (p is a prime) is said to be strong homogeneous if it has the form xid-1+xid-2xj+xid-3xj2+⋯+xjd-1≡0modpn,where p∤d,d>np∤d,d>n and i,j∈{1,2,…,t},i≠ji,j∈{1,2,…,t},i≠j. A strong homogeneous equation over a finite field Fpn,pn>2Fpn,pn>2, is defined analogously. For a system S   of strong homogeneous congruences (or equations), the associated graph G(S)G(S) of S   is defined to be the graph whose vertex set is {x1,x2,…,xt}{x1,x2,…,xt} and two vertices xixi and xjxj are adjacent whenever they belong to a congruence (or equation) in S. We show that the solutions of S   have a close relation with the vertex colourings of G(S)G(S). The number of solutions of S   can be represented by the chromatic polynomials of the components of G(S)G(S). This implies that the problem of finding the solutions to a system of equations over a finite field or congruences is NP-hard, even for a very special class. An asymptotic estimation to the number of the solutions of the system of SH-congruence is also established.