Soluciones racionales de sistemas de ecuaciones diagonales y su aplicación al "subset sum problem"

FRANCISCO GOTTIG; MARIANA PÉREZ; MELINA PRIVITELLI

Neuquén

Congreso; Reunión Anual de la Unión Matemática Argentina, UMA 2022; 2022

Universidad Nacional del Comahue

Sea Fq el cuerpo finito de q elementos. Un sistema de ecuaciones diagonales generalizadas es un sistema de la forma:(1) a_{j1}x_1^d_1+⋯+a_{jt}x_t^d_t=g_j(x1,...,xk), 1\leq j\leq n, con k≤t, g:1,...,g_n ∈ Fq[x1...,xk], grado(g_j)>d_{t−1}>⋯>d_1>1.Diversos problemas de teoría de códigos, criptografía y combinatoria sobre cuerpos finitos requieren estimar o poder garantizar la existencia de soluciones racionales (soluciones con coordenadas en Fq ) de sistemas de la forma (1) (ver, por ejemplo, [1] y [2]). Para el caso particular de una única ecuación diagonal existen muchos resultados, incluso hay fórmulas de conteo exacto de soluciones racionales para ecuaciones especiales. En [3] las autoras proporcionan estimaciones y resultados de existencia para variantes de ecuaciones diagonales. En cambio, cuando se trata de sistemas, se encuentran muchos menos resultados. En [4] las autoras estudian un caso particular de (1) que se trata de los sistemas en los que d_{ji}=d_{ki} si k≠j para 1≤i≤n y obtienen resultados que mejoran en diversos aspectos los de [5] y [6].En este trabajo estudiamos la siguiente versión de (1): consideramos d_{ij}=d_{ik} para k≠j, 1≤i≤n y g_i ∈ Fq para todo 1≤i≤n. Nuestro interés en este sistema radica en que en primer lugar no se cuenta con resultados de existencia ni estimaciones de la cantidad de soluciones racionales del mismo y por otro lado en que el estudio del conjunto de sus soluciones racionales tiene aplicaciones a diferentes problemas en cuerpos finitos como, por ejemplo, el "Subset Sum Problem" y el estudio de los deep holes en el código de Reed Solomon. Nuestra metodología consiste en considerar la variedad algebraica definida por los polinomios f_j= a_{j1}x_1^d_1+⋯+a_{jt}x_t^d_t-b_j para 1≤j≤n y estudiar las propiedades geométricas de la misma. A partir de este estudio se obtienen estimaciones y resultados de existencia de soluciones racionales del sistema. Finalmente aplicamos los resultados obtenidos al estudio del "Subset Sum Problem" sobre cuerpos finitosReferencias:.[1] R. Lidl y H. Niederreiter. Finite fields, Adisson-Wesley, Reading, Massachusetts, 1983.[2] Gary L. Mulln y Daniel Panario, Handbook of Finite Fields (1st ed.), Chapman and Hall/CRC, 2013.[3] M. Pérez y M. Privitelli, Estimates on the number of rational solutions of variants of diagonal equations over finite fields, Finite Fields and Appl. 68,(2020), pp. 30.[4] M. Pérez y M. Priivitelli, on the number of solutions of systems of certain diagonal equations over finite fields, Journal of Number Theory 236 (2022), 160-187.[5] K. W. Spackman, Simultaneous solutions to diagonal equations over finite fields, J. Number Theory 11 (1979), 100-115.[6] K. W. Spackman, On the number and distribution of simultaneous solutions to diagonal congruences, Canadian J. Math 33 (1981), no. 2. 421-436.