Hermitian sum of squares multipliers on finite subsets of C^n

Abstract

The study of hypercube nodes is one of the most important topics in computer science, since this set is the domain of Boolean functions. They are the functions that associate each length?n binary vector, or string, into a single binary value, or bit. These functions are present in many fields such as learning theory, coding theory, social choice theory, graph theory and more.The study of the coordinate ring of hypercube nodes constitutes a generalization of the study of Boolean functions. In 2016, Bleckhermann, Gouveia and Pfeifer gave upper and lower bounds to certificate the non-negativeness of polynomials in the coordinate ring of hypercube nodes. In this text, we generalize the conditions exposed in Theorem 1.1[3] by Bleckherman, Gouveia and Pfeiffer for finite subsets of finite dimensional complex vector spaces. Based on their result, we give an upper bound for hermitian sum of squares multipliers related to the finite set U := U_d × · · · × U_d, which is defined as the cartesian product of n copies of U_d, the set of d-th roots of unity. Finally, we present a brief application of this idea to the graph coloring problem.

El estudio de los nodos del hipercubo es uno de los temas más importantes en ciencias computacionales, pues, este conjunto es el dominio de las funciones Booleanas. Estas son las funciones que asocian cada vector binario de n entradas a un único valor binario o bit. Estas funciones están presentes en muchos campos relevantes del conocimiento como inteligencia artificial, teoría de códigos, teoría de elección social y teoría de grafos, entre otras. El estudio del anillo coordenado de los nodos del hipercubo constituye una generalización del estudio de las funciones booleanas. En 2016, Bleckhermann, Gouveia y Pfeifer dieron cotas superiores e inferiores en los grados polinomiales para certificar la no-negatividad de polinomios en el anillo coordenado de los nodos del hipercubo. En este texto, nosotros generalizamos las condiciones expuestas en el primer teorema hecho por Bleckhermann, Gouveia y Pfeifer para subconjuntos finitos de espacios vectoriales finito dimensionales y complejos. Basados en su resultado, nosotros damos una cota superior para multiplicadores de sumas de cuadrados hermitianos en el anillo coordenado del conjunto finito U. Este conjunto es definido como el producto cartesiano de n copias de las raíces d-ésimas de la unidad. Finalmente, nosotros presentamos una breve aplicación de esta idea al problema de coloración de grafos.