El problema de Frobenius para semigrupos numéricos

Por: José Carlos Rosales González (Departamento de Álgebra de la UGR).

El llamado problema de las monedas (Coin exchange problem) consiste en el siguiente: supongamos que en un país tenemos sólo monedas de valores 5, 7 y 11 unidades. Supongamos que vamos a una tienda y compramos un producto que vale 28 unidades. Entonces podemos pagarlo con dos monedas de 5, una de 7 y otra de 11. Sin embargo, si el producto vale 19 unidades, entonces no es posible encontrar una combinación de las monedas para llegar a la cantidad exacta de 19. La pregunta es ¿cuál es el mayor valor de producto (número) que no puede ser pagado con sólo monedas de 5, 7 y 11 unidades?

La formulación matemática de dicho problema es la siguiente. Sea N el conjunto de los números enteros no negativos. Un semigrupo numérico es un subconjunto de N que es cerrado para la suma, contiene al cero y tiene complemento finito en N.

Si A es un subconjunto no vacío de N, entonces denotaremos por \langle A \rangle al submonoide de N generado por A, esto es,
\langle A \rangle =\{\lambda_1a_1+\ldots+\lambda_n a_n;n\in\mathbb{N}-\{0\}, \lambda_i\in \mathbb{N}, a_i\in A\}. Es fácil de probar que \langle A \rangle es un semigrupo numérico si y sólo si el máximo común divisor de los elementos de A vale 1 ([1]).

Sean n_1,\ldots,n_p enteros positivos tales que m.c.d\{n_1,\ldots,n_p\}=1. Frobenius (1849-1917) propuso a sus alumnos el problema de encontrar una fórmula que permitiese determinar a partir de n_1,\ldots,n_p el máximo entero que no pertenece a \langle n_1,\ldots,n_p \rangle. Él también planteó la cuestión de determinar cuántos enteros positivos no pertenecen a \langle n_1,\ldots,n_p \rangle. Estos dos números son conocidos como el número de Frobenius y el género del semigrupo numérico \langle n_1,\ldots,n_p \rangle y lo denotaremos por F(\langle n_1,\ldots,n_p \rangle) y g(\langle n_1,\ldots,n_p \rangle) , respectivamente.

Sylvester en [3] resuelve los problemas citados anteriormente por Frobenius para el caso p=2. En concreto, prueba que F( \langle n_1,n_2 \rangle )=n_1 n_2-n_1-n_2 y g( \langle n_1,n_2 \rangle)=\frac12(n_1-1)(n_2-1). En el ejemplo inicial, si tenemos monedas de 5 y 7 unidades, entonces el el mayor valor que no puede ser pagado con monedas de 5 y 7 unidades es 23. Y hay exactamente 12 números que no pueden ser expresados como combinación de 5 y 7, a saber: 1,2,3,4,6,8,9,11,13,16,18,23.

En la actualidad estos problemas siguen abiertos para p\geq 3 . Pese a ello ha habido numerosos progresos en este campo. El lector interesado puede consultar algunos textos recientes como [1] y [2] para hacerse una idea bastante aproximada del estado en que se encuentra esta línea de investigación.

Referencias

[1] J. L. Ramírez-Alfonsín, The Diophantine Frobenius Problem, Oxford University Press. London, 2005.

[2] J. C. Rosales, P. A. García-Sánchez, Numerical Semigroups, Springer, New York, 2009.

[3] J. J. Sylvester, Excursus on rational fractions and partitions, Amer. J. Math. 5 (1882), 119-136.

___________________________

José Carlos Rosales González es Catedrático de Universidad en el Departamento de Álgebra de la UGR. Es miembro del comité editorial del Journal of Mathematical Inequalities y su línea de investigación es en Semigrupos Conmutativos. Es muy aficionado a los bailes de salón.