Algebra and Discrete Mathematics Seminar

Factorization and the Half-Factorial Property

Jim Coykendall — Clemson University

The notion of unique factorization is central in commutative algebra and number theory (with very important ramifications spilling over into almost every branch of mathematics). In general, “factorization” may be considered the study of the multiplicative decomposition(s) of elements in a ring (usually an integral domain for our purposes), and generalizations of unique factorization are of much interest.

One of the most infamous generalizations of unique factorization is the half-factorial property. Loosely speaking, a half-factorial domain is an integral domain in which elements may not factor uniquely, but any two decompositions of the same nonzero element into irreducibles will have the same number of irreducibles involved (counting possible multiplicities). The aim of this talk will be to give an overview of this generalization of unique factorization from its inception through some very recent results. Along the way, the talk will be seasoned and flavored with many examples comparing and contrasting the half-factorial property with the more familiar notion of unique factorization. Graduate students are especially encouraged to have their lives changed by this talk!

Efficient Fully Homomorphic Encryption Schemes

Shuhong Gao — Clemson University

As cloud computing, internet of things (IoT) and blockchain technology become  increasingly  prevalent, there is an urgent need to protect the privacy of massive volumes of  sensitive data collected or stored in distributed  computer networks  or cloud  servers,  as many of the networks or servers can be vulnerable to external and internal threats such as malicious hackers or curious insiders.   The Holy-Grail of cryptography is to have practical fully homomorphic encryption (FHE) schemes that allow any third party (including cloud servers, hackers, miners or  insiders) to perform searching or analytics of an arbitrary function on encrypted data without decryption, while no information on the original data is ever leaked. The breakthrough was made by Gentry in 2009  who discovered the first FHE scheme, and since then  many improvements have been made on designing more efficient homomorphic encryption schemes.  The main bottlenecks are in bootstrapping and large cipher expansion factor (the size ratio of ciphertexts over messages): the current best FHE schemes compute bootstrapping of one bit operation in 0.013 second and still have a cipher expansion factor of 10,000. In this talk, we present a compact  FHE scheme whose  bootstrapping speed is slightly slower but  whose cipher expansion factor  is  only 6  under private-key  encryption  and 20  under public-key encryption,  hence practical in term of storage.

Minimal Ramification Problem

Cynthia Ramiharimanana — Clemson University

Minimal ramification problem can be considered as a quantitative version of Inverse Galois Problem. The latter is a question that asks whether every finite group is a Galois group of a Galois extension of the field of rational numbers Q. It is one of the important problems in Field Arithmetic and Algebraic Number Theory. For a given finite group G, let Ram(G) be the minimal integer for which there exists a Galois extension of N/Q that ramifies exactly at Ram(G) primes. The task in minimal ramification problem is to compute or to bound Ram(G). In this talk, I will give an overview of the problem and some results, and then we will talk about current and future research.

Lattice Cryptography and Attacks

Benjamin Case – Clemson University

In this seminar we will overview lattice cryptography and its usefulness for post-quantum security and fully homomorphic encryption. In particular, we will look at the security of schemes based on the Learning with Errors (LWE) problem. Discrete probability distributions defined over rings and finite fields play an important role in the security of lattice-based schemes; and through studying how linear combinations of these distributions behave, we will reveal some weak instances of the LWE problem that are not suitable for building encryption schemes.

Coloring geometric intersection graphs

Csaba Biro – University of Louisville

Many classical hard algorithmic problems on graphs, like coloring, clique number, or the Hamiltonian cycle problem can be sped up for planar graphs resulting in algorithms of time complexity $2^{O(\sqrt{n})}$. We study the coloring problem of unit disk intersection graphs, where the number of colors is part of the input. We conclude that, assuming the Exponential Time Hypothesis, no such speedup is possible. In fact we prove a series of lower bounds depending on further restrictions on the number of colors. Generalizations for other shapes and higher dimensions were also achieved. Joint work with E. Bonnet, D. Marx, T. Miltzow, and P. Rzazewski.

Refreshments at 3:00, Martin-O, first floor.

Hopf Algebra Action on some AS-Regular Algebras of Small Dimension

Luigi Ferraro – Wake Forest University

The classical Chevalley-Shephard-Todd Theorem gives a characterization of when a group acting linearly on the commutative polynomial ring has a ring of invariants that is isomorphic to a polynomial ring. Understanding when group actions (or more generally, Hopf actions) on AS-regular algebras give AS-regular invariant rings has proven to be a difficult problem. We pro- vide some new examples of Hopf actions on some AS-regular algebras such that the ring of invariants is also AS-regular.

Refreshments at 3:00, Martin-O, first floor. (Note that this talk is on a Tuesday.)

Sorting Index and Mahonian-Stirling pairs for labeled forests

Amy Grady, Clemson

Björner and Wachs defined a major index for labeled plane forests and showed that it has the same distribution as the number of inversions. We will define and study the distributions of a few other natural statistics on labeled forests. Specifically, we introduce the notions of bottom-to-top maxima, cyclic bottom-to-top maxima, sorting index and cycle minima. Then we show that the pairs (inv, Btmax), (sor, Cyc), and (maj, Cbtmax) are equidistributed. Our results extend the result of Bj¨orner and Wachs and generalize results for permutations.

Properties of the Promotion Markov Chain on Linear Extensions

Kara Stasikelis, Clemson

The Tsetlin library is a model for the way an arrangement of books on a library shelf evolves over time. It assumes that, given n books, one book is read and returned at the end of the shelf before another one is picked up. Suppose the probability that a book i is picked up is x_i. An interesting property of this Markov chain is that its eigenvalues can be computed exactly and they are linear in the x_i ‘s. This result has been generalized in various ways by various people. In this work, we investigate the extended promotion Markov Chain introduced by Ayyer, Klee, and Schilling in 2014. They showed that for a poset that is a rooted forest, the transition matrix has eigenvalues that are linear in x_1,…, x_n. We show the same result for a larger class of posets.

Ideal class (semi)groups and factorization in Prüfer domains

Richard Hasenauer – Northeastern State University

The ideal class group helps explain factorization properties in Dedekind domain.   Can we use the ideal class group to gain information about factorization in generalizations of Dedekind domain?    After exploring this question, we will turn our attention to the task of computing an ideal class semigroup.   We will then discuss what information about factorization can be obtained from the ideal class semigroup.

Refreshments at 3:00 in the Martin-O foyer

Lattice ideals and coding theory

Hiram Lopez Valdez – Clemson University

By issues of the destiny, in the world of mathematics there are two (at least) different objects called “lattices”. One of them is related with the concept of an ordered set and we will not talk about this one. Another object which is also called a lattice is just defined as a subgroup of Z^n. Given a lattice L, we associate a binomial ideal I(L) called “lattice ideal”.

We will study some of the main properties of lattice ideals, for instance given a set of generators of L, how to find I(L), and given a set of generators of I(L), how to find L. We will see also how to identify if an arbitrary binomial ideal comes from a lattice, and if this is the case, how to find such a lattice.

Finally, we will see how we can apply lattice ideals to coding theory.

Ideal Graphs and Adjacency Conditions

Jim Coykendall, Clemson

Recently there has been much activity in the intersection of commutative algebra and graph theory. In particular, there has been much attention to the so called “zero-divisor graph” and a number of its natural variants. The idea behind the zero-divisor graph is to take as vertices the nonzero zero-divisors of a commutative ring with identity and declare that there is an edge between $x,y\in R$ if and only if $xy = 0$. There are a number of striking properties that this graph possesses, probably the most interesting of which is that this graph is connected and has diameter no more than 3.

In this talk we expand this idea to a larger arena. In particular, we fix a commutative ring and define a graph by letting the vertex set be (a subset of) the set of ideals. Under various defining conditions for edges, we determine properties of the graph that lend insights to the algebraic structures involved.