Session on Finite Fields:
Monday, August 5
14.30-15.00
Horacio Tapia (UAM-Iztapalapa, México)
Elementos idempotentes en una clase de anillos conmutativos
Es bien sabido que los códigos cíclicos de longitud $n$ (y algunas generalizaciones de estos como los constacíclicos), definidos sobre diversos anillos que incluyen campos y anillos de cadena finitos, $R$, se pueden identificar con ideales del anillo $R[x]/\langle x^n-1 \rangle$. Estos ideales se pueden describir por medio de un conjunto de generadores y en algunos casos por un solo generador (principales), siendo otra forma por medio de elementos idempotentes del anillo. Ambas formas tiene sus ventajas dependiendo del estudio que se realice de estos códigos. Por ejemplo, el conocer elementos idempotentes generadores de un código cíclico permite saber si este es un códigos LCD (Linear Complementary Dual). En general, determinar elementos idempotentes en un anillo $A$ (finito conmutativo) no es una tarea fácil. En esta plática se presenta un método para determinar tales elementos a partir de elementos idempotentes de un anillo cociente $A/N$ donde $N$ es un ideal nilpotente del anillo $A$ y $A$ tiene una sucesión de ideales con ciertas propiedades. Ejemplos de esta clase de anillos incluye anillos de grupo, $AG$, donde $A$ es un anillo finito de cadena y $G$ un grupo finito conmutativo. (Con la colaboración de F. Dinitz de Melo-Hernández y J.C. Hernández).
15.00-15.30
Ricardo Conceição (Gettysburg College, USA)
On MVSPs taking on three values
Let $q$ be a power of a prime, and for any non-constant polynomial $F\in\mathbb{F}_q[x]$, let $V_F=\{F(\alpha): \alpha \in \mathbb{F}_q\}$ be its value set. One can easily show that $V_F$ satisfies $$ (1)\quad\quad\quad\left\lfloor\dfrac{q-1}{\deg F}\right\rfloor +1 \leq |V_F| \leq q, $$ where $\left\lfloor n \right\rfloor$ is the greatest integer $\leq n$, and $ |\mathcal{S}|$ denotes the cardinality of the set $\mathcal{S}$. Polynomials attaining the lower bound in (1) are called minimal value set polynomials (shortened to MVSP).
In this talk we discuss how a classification of Lacunary polynomials by L. Rédei can be used to classify MVSPs which split completely over the base field and whose value set has three elements.
15.40-16.10
Ariane Masuda (City University of New York, USA)
Isomorphism of graphs associated with Rédei functions
Let $\mathbb{F}_q$ be a nonbinary field. We fix $a\in\mathbb{F}_q^*$ and a positive integer $n$. For $x\in \mathbb{F}_q \cup\{\infty\}$, the Rédei function can be defined by $R_n(x, a) = \sqrt{a}\dfrac{(x+\sqrt a)^n+(x-\sqrt a)^n}{(x+\sqrt a)^n-(x-\sqrt a)^n}$. In 2015, Qureshi and Panario provided a description of the functional graphs associated with Rédei functions based on the dynamics of the multiplication map on cyclic groups. By using the conditions on the isomorphism of graphs of multiplication maps obtained by Deng in 2013, we investigate when graphs of Rédei functions are isomorphic. As a result, we obtain infinite families of isomorphic graphs associated with Rédei permutations. In particular, we describe all involutions that are isomorphic. This is joint work with Juliane Capaverde and Virgínia Rodrigues.
16.10-16.40
Luis Medina (University of Puerto Rico, Puerto Rico)
Value distribution of elementary symmetric polynomials and their perturbations over finite fields
In this talk we establish the asymptotic behavior of generating functions related to the exponential sum over finite fields of elementary symmetric functions and their perturbations. This asymptotic behavior allows us to calculate the probability generating function of the probability that the the elementary symmetric polynomial of degree $k$ (and its perturbations) returns $\beta\in\mathbb{F}_q$, where $\mathbb{F}_q$ represents the field of $q$ elements.
17.10-17.40
Gina Gallegos (IPN, México)
Efficient computations in the ring of integer polynomials \(\mathcal{R}_q\) module $X^n+1$
The evolution of computing power has led from the imminent arrival of quantum computers to the start of the NIST Post-quantum standardization process in 2017. Considering that security of the modern cryptography may be broken in polynomial time, in such a standardization process, new standards for encryption, signature and key encapsulation mechanism are being discussed. All of them can be classified depending the security problem they are based on, as in example: Codes, hashes, polynomials with multiple variables, isogenies of supersingular elliptic curves and lattices. Some of the schemes that base their security on this last one, perform computations in the ring of integer polynomials \(\mathcal{R}_q\) with \(\mathcal{R}_q = \mathbb{Z}_q[X]/(X^n+1)\), $n = 512$ or $1024$ and $q = 12289$ where each coefficient is reduced modulo $q$. In this talk I will discuss about how such computations are enabled efficiently by using the Number Theoretic Transform (NTT) in order to transform polynomials into Fourier space. (In collaboration with Jesus-Javier Chi-Dominguez, Olimpia Saucedo-Estrada, Alfonso F. De Abiega-L'Eglisse, Kevin A. Delgado-Vargas and Luis Alberto Rivera-Zamarripa).
Tuesday, August 6
14.30-15.00
Florian Luca (University of the Witwatersrand, South Africa)
Fibonomials modulo $p$
We say that a set $X$ of numbers is an additive bases of finite order $k$ for a prime $p$ if every residue class modulo $p$ can be represented as $x_1+x_2+\cdots+x_k\pmod p$ where $x_i\in X$ for $i=1,\ldots,k$. In my talk, I will survey results about sets of combinatorial objects which are known to be additive bases modulo $p$ either for every prime number $p$, or for a set of prime numbers $p$ of asymptotic density $1$ as a subset of all then primes. These include middle binomial coefficients, Catalan numbers, products of two factorials, Apery numbers and values of the Ramanujan $\tau$-function. We will also present a new result to the effect that the set of Fibonomials ${n\choose k}_F$ forms an additive basis of order $8$ for most primes $p$. Here, the Fibonomial coefficient ${n\choose k}_F$ is defined as ${\displaystyle{\frac{n!_F}{k!_F (n-k)!_F}}}$, where $n!_F=F_1F_2\cdots F_n$ and $F_m$ is the $m$th Fibonacci number. The proofs use results from additive combinatorics. This is joint work with Victor García.
15.00-15.30
María Chara (Universidad Nacional del Litoral, Argentina)
An optimal recursive tower over the field with 4 elements with mixed variables
In this talk we introduce an optimal quadratic recursive tower $\mathcal{E}$$=(E_0, E_1, ...)$ over $\mathbb{F}_4$ whose field extensions $E_{i+1}/E_i$ are Artin-Schreier extensions but the tower itself is not recursively defined by an Artin-Schreier equation. To prove the optimality of this tower we use a simple but powerful systematic method, that we will also present in this talk, to construct proper recursive subsequences and supersequences of functions fields from other recursive sequences. This is a joint work with R. Toledano (Universidad Nacional del Litoral, Argentina) and H. Navarro (Universidad del Valle, Colombia).
15.40-16.10
Cicero Carvalho (Universidade Federal de Uberlândia, Brasil)
On some evaluation codes defined on higher dimensional scrolls
We will present a class of projective Reed-Muller type codes defined by evaluating a space of homogeneous polynomials in the points of a higher dimensional scroll. We determine a formula for the dimension of these codes and the exact value of the minimum distance in some special cases. This is a joint work with Victor G.L. Neumann, Xavier Ramírez-Mondragón and Horacio Tapia-Recillas.
16.10-16.40
Ismael Gutiérrez (Universidad del Norte, Colombia)
Cliques in projective space and construction of cyclic Grassmannian Codes
Cyclic Grassmannian codes were first presented by A. Kohnert and S. Kurz from the perspective of design theory over finite fields. Later T. Etzion and A. Vardy defined them as a $q$-analog of cyclic code from the classical coding theory. J. Rosenthal et al. and H. Gluesing et al. studied cyclic codes from the point of view of groups actions. Specifically, they have used an action of the general linear group over a Grassmannian to define them: these codes were called cyclic orbits codes. Cyclic Grassmannian codes are a special case of orbits codes.
Recently T. Etzion et al., K. Otal et al., B. Chen, and H. Liu presented new methods for constructing such codes, what includes linearized polynomials, namely subspace polynomials and Frobenius mappings.
A computational method for construction of cyclic Grassmannian codes was given by Gutierrez and Molina. Construction of Grassmannian codes in some projective space is highly mathematical and requires strong computational power for the resulting searches. In this talk, we present a new technique to construct subspace codes. We use some cliques in projective space $\mathbb{P}_q(n)$ to produce cyclic Grassmannian codes.
We denote with $\mathbb{P}_q(n)$ the projective space of order $n$, that is, the set of all subspaces of $\mathbb{F}_q^n$, including the null space and $\mathbb{F}_q^n$ itself. For a fixed natural number $k$, with $0\leq k\leq n$ we denote with $G_q(n,k)$ the set of all subspaces of $\mathbb{F}_q^n$ of dimension $k$ and we call it the $k$-Grassmannian over $\mathbb{F}_q$ or Grassmannian in short. We say that $\mathscr{C}\subseteq G_q(n,k)$ is an $(n,M,d,k)_q$ Grassmannian code if $|\mathscr{C}| = M$ and $d(X,Y)\geq d$ for all distinct $X,Y\in \mathscr{C}$. Such a code is also called a constant dimension code.
Let $\mathcal{A}_q(n,d,k)$ and $\mathcal{C}_q(n,d,k)$ be the maximum number of codewords in an $(n,M,d,k)_q$ grassmannian code over the filed $\mathbb{F}_q$ and the maximum number of codewords in an $(n,M,d,k)_q$ cyclic code over $\mathbb{F}_q$, respectively. It is clear that $\mathcal{C}_q(n,d,k)\leq \mathcal{A}_q(n,d,k)$.
Let $\alpha\in \mathbb{F}_{q^n}^\ast$ and $V\in G_q(n,k)$. The cyclic shift of $V$ is defined as follows: \[\alpha V := \{\alpha v\mid v\in V\}.\] Clearly $\alpha V$ is a subspace belonging to $G_q(n,k)$. That is, it has the same dimension as $V$. A Grassmannian code $\mathscr{C}\subseteq G_q(n,k)$ is called \texttt{cyclic}, if for all $\alpha\in \mathbb{F}_{q^n}^\ast$ and all subspace $V\in \mathscr{C}$ we have that $\alpha V\in \mathscr{C}$. The set $\mathcal{O}rb(V) :=\{\alpha V\mid \alpha\in \mathbb{F}_{q^n}^\ast\}$ is called the \texttt{orbit} of $V$. Observe that in this definition the zero vector was omitted from the set of an orbit. Starting now, this will be explicitly deleted when we specify the elements of a codeword of a cyclic Grassmannian code.
If $V\in G_q(n,k)$, then $|\mathcal{O}rb(V)| = \tfrac{q^n-1}{q^t-1}$, for some natural number $t$, which divides $n$.
Theorem $$\mathcal{C}_q(n,d,k)=\sum_{t\mid n}{\alpha_t\frac{q^n-1}{q^t-1}}$$ for some integer $0\leq\alpha_t$.
A clique of an undirected graph $G$ is a complete subgraph of $G$; that is, A clique is a subset of vertices of $G$ such that every two distinct vertices in the clique are adjacent. The clique of the largest possible size is referred to as a maximum clique; that is, it cannot be extended by including one more adjacent vertex. The clique number $\omega(G)$ of G is the number of vertices in a maximum clique in $G$. A clique of size $k$ is called a $k$-clique.
To calculate the coefficients $\alpha_t$ in the previous theorem we proceed as follows:
1. Find all the orbits of $ G_q (n, k) $ and denote this set by $\mathfrak{O}$. That is, \[\mathfrak{O} := \{\mathcal{O}rb(V) \mid V\in G_q(n,k)\}.\]
2. Calculate the minimum subspace distance $d_{\mathcal{O}rb(\cdot)}$ of each orbit independently; then we form the pair $(\mathcal{O}rb(\cdot), d_{\mathcal{O}rb(\cdot)})$.
3. A minimum distance $d$ is fixed, for which we want to obtain a cyclic code.
4. The graph $\mathcal{G} = (\mathcal{O,E})$ is constructed so that the set $\mathcal{E}$ of edges is obtained in the following way: two orbits are adjacent if their union has a minimum distance greater or equal than $d$.
5. A clique in the graph $\mathcal{G}$ constructed in (4) is a Grassmannian cyclic code with minimum distance $d$ and dimension $k$.
6. To determine the maximum values of each $\alpha_t$, the graph $\mathcal{G}$ is separated into independent subgraphs by the number of spaces in their orbits (every vertex in each subgraph with the same number of associated spaces), and the number of cliques in each one is calculated.
(In collaboration with Ivan Molina Naizir).
17.10-17.40
Sandra Díaz Santiago (IPN, México)
Una aplicación de secreto compartido
Un esquema de secreto compartido es un mecanismo, para compartir un secreto entre un grupo de participantes. El primer esquema de este tipo fue propuesto por Shamir en 1979 y consiste en dividir un secreto $K$ en $w$ partes que se les entregan a $w$ participantes. El secreto $K$ podrá recuperarse si se tienen al menos $u \leq w$ partes, pero no será posible reconstruirlo con menos de $u$ partes. En esta charla, se presentará un protocolo criptográfico para el intercambio seguro de llaves. Aunque ya existen soluciones bien conocidas con este propósito, como el protocolo Diffie-Hellman o el uso de una infraestructura de clave pública, éstas pueden resultar costosas en ciertos escenarios. El protocolo criptográfico propuesto, utiliza el esquema original de Shamir sobre un campo primo, para intercambiar una clave de manera segura, bajo el supuesto de que el enemigo es un programa de cómputo y no un ser humano.