New characteristic dependent linear rank inequalities

Abstract

En este trabajo estudiamos como construir desigualdades rango lineales dependientes de la característica y sus aplicaciones a la Teoría de Codificación de Redes y a la Teoría de Repartición de Secretos en protocolos criptográficos. Proponemos dos métodos que aprovechan la existencia de ciertas matrices binarias. El primer método está basado en la construcción de ciertos espacios vectoriales complementarios y tiene aplicaciones directas a la Teoría de Codificación de Redes. Presentando así, entre las aplicaciones y usando problemas de programación lineal, que para cada conjunto finito o cofinito de números primos P, existe una sucesión de redes (N(t)), en la cual cada miembro es soluble linealmente sobre un cuerpo finito si, y sólo si, la característica del cuerpo está en P; además, la capacidad lineal sobre cuerpos cuya característica no está en P, tiende a 0, cuando t tiende a infinito. El segundo método está basado en la construcción de ciertos espacios que se comportan en cierta forma como un esquema de repartición de secretos y tiene aplicaciones directas en la Teoría de Repartición de Secretos; calculamos cotas inferiores de radios de información lineal de algunas estructuras. Adicionalmente, proponemos una extensión del problema de solubilidad de un operador de clausura. Estudiamos la capacidad de un operador de clausura y una serie de problemas de programación lineal cuyas soluciones son cotas superiores sobre esta capacidad; este problema está relacionado al cálculo de capacidades de redes de uniemisión múltiple.

In this work, we develop some methods for producing characteristic-dependent linear rank inequalities and show some applications to Network Coding and Secrets Sharing. We propose two methods that take advantage of the existence of certain binary matrices. The first method is based on the construction of certain complementary vector spaces and has direct applications to Network Coding. Using linear programming problems, for each finite or co-finite set of primes P, we show as application that there exists a sequence of networks (N(t)) in which each member is linearly solvable over a finite field if and only if the characteristic of the field is in P; and the linear capacity over fields whose characteristic is not in P, tends to 0 as t tends to infinity. The second method is based on the construction of certain spaces that behave in a certain way as a linear secret sharing scheme and has direct applications in Secret Sharing; we calculate lower bounds on the linear information ratios of some access structures. Additionally, we propose an extension of the solubility problem of a closure operator. We study the capacity of a closure operator and a class of linear programming problems whose optimal solutions are upper bounds on this capacity; this problem is related to the calculation of capacities of multiple-unicast networks.