Skip to Main Content

Algebra, Geometry, and Cryptology Seminar Archives

The following are archives of the Algebra, Geometry, and Cryptology Seminar at Boise State University.

Fall 2018


Organized by Zach Teitler.

August 24

Open Problem Discussion & planning
An informal sharing and discussion of open problems. All seminar participants are encouraged to bring open problems and puzzles to share, especially recently learned ones.

August 31

Scott Andrews, Boise State University
Schur functions
The ring of symmetric functions appears in many areas of mathematics. In particular, many problems in combinatorics and representation theory can be phrased in terms of symmetric functions. I will explain what a symmetric function is and talk about a particularly useful basis of the ring of symmetric functions, the Schur functions.

September 7

Topology seminar
Jens Harlander, Boise State University
Some conjectures in 2-dimensional combinatorial topology

September 14

Zach Teitler, Boise State University
A bound for the Waring rank of the determinant via syzygies
The Waring rank of the $3 \times 3$ generic determinant is known to be greater than
or equal to $14$, and less than or equal to $20$. Proofs of the lower bound of $14$ were
given in terms of geometric singularities or the Hilbert function of the apolar ideal.
We improve the lower bound to $15$ by considering higher syzygies
in the minimal graded free resolution of the apolar ideal of the determinant.
This is joint work with Mats Boij.

September 21

No seminar.

September 28

Topology seminar
Jens Harlander, Boise State University
What is homological group theory?

October 5

Zach Teitler, Boise State University
A theorem of Polya on polynomials
I will present a nice theorem of Polya about polynomials: the sets of small values of complex polynomials cast small shadows. This is taken from “Proofs from THE BOOK” by Aigner and Ziegler.

October 12

Sam Coskey, Boise State University
On splitting families
A set $A$ splits an even-sized set $B$ if $A$ contains exactly half the elements of $B$. For a natural number $k$, a splitting family on $k$ is a collection of sets that splits any even-sized subset of $\{1,\dotsc,k\}$. Variations on the concept of splitting families have appeared in applications of combinatorial search. We investigate the number of sets needed to make a splitting family on $k$. We give some examples and computational results, as well as theoretical partial results identifying the exact number under certain assumptions. This represents work from the Summer 2018 REU CAD, with Bryce Frederickson, Sam Mathers, and Hao-Tong Yan.

October 19

No meeting this week.

October 26

Topology seminar
Kennedy Courtney, Boise State University
Topological Invariants of Food Webs

November 2

No meeting this week.

November 9

No meeting this week.

November 16

Scott Andrews, Boise State University
Frobenius Groups
A Frobenius group is a finite group that has an action on a set satisfying certain properties. In 1901, Frobenius used representation theory to prove that all Frobenius groups can be decomposed as a semidirect product; there is still no known proof of this fact that avoids representation theory. I will introduce Frobenius groups and a little bit of representation theory, then prove the theorem of Frobenius.

November 30

Topology seminar
Uwe Kaiser, Boise State University
Topological complexity and motion planning

December 7

No meeting.

Spring 2018


Organized by Zach Teitler

January 12

Planning

January 19

Topology Seminar
Jens Harlander, Boise State University
Who cares about finite topological spaces? Part I

January 26

Topology Seminar
Jens Harlander, Boise State University
Who cares about finite topological spaces? Part II

February 2

Topology Seminar
Jens Harlander, Boise State University
Who cares about finite topological spaces? Part III

February 9

Mathematics Colloquium

February 16

Mathematics Colloquium

February 23

Jonny Comes, College of Idaho
An introduction to cellular algebras
In the mid 1990s Graham and Lehrer introduced the notion of a cellular algebra. Roughly speaking, a cellular algebra is a ring equipped with a basis that, in some sense, behaves nicely with respect to multiplication. In this talk I will start with the precise definition of a cellular algebra. Then I will explain how the cellular basis can be used to classify irreducible representations of the algebra. The main examples for the talk are the Temperley-Lieb algebras. I will describe a cellular basis of these algebras, and the corresponding classification of irreducible representations. If time permits I will also discuss a cellular basis for the group algebra of the symmetric group and its relationship to the Robinson–Schensted–Knuth algorithm.

March 2

Scott Andrews, Boise State University
The Robinson-Schensted correspondence
The Robinson-Schensted correspondence is a bijection between permutations and pairs of standard Young tableaux. I will talk about standard Young tableaux (in particular why we care about them) and present the bijection. Time permitting I will look at some properties, consequences, and generalizations of the correspondence.

March 9

Zach Teitler, Boise State University
Sperner’s Theorem and the Erdos-Ko-Rado Theorem
Sperner’s theorem of 1928 answers the question: how many subsets of {1,2,…,n} can we choose so that none of the subsets are contained in each other?

Nearly oppositely, we can ask: how many subsets of {1,2,…,n} can we choose so that each pair of the subsets meets, i.e., has a nonempty intersection? Most interestingly, how many such subsets can we choose if the subsets have to meet pairwise and also all have to have the same number of elements, k? The answer is given by the Erdos-Ko-Rado theorem, which was found in 1938, but not published until 23 years later.

Both of these have numerous generalizations, including q-analogs.

March 16

Topology Seminar
Uwe Kaiser, Boise State University
Categorification in Algebra and Topology

March 23

No meeting (Spring Break).

April 6

Topology Seminar
Jens Harlander, Boise State University
Finite or Infinite?

April 13

Jonny Comes, College of Idaho
Frobenius algebras and 2D TQFTs
A Frobenius algebra is a finite-dimensional algebra equipped with a nondegenerate bilinear form compatible with the multiplication. Examples include matrix rings, group algebras, and artinian Gorenstein rings. Frobenius algebras have been studied by representation theorists since the 1930s. More recently, these algebras have become popular outside of representation theory because of their connection to topological quantum field theory. In this talk I will discuss the connection between 2 dimensional topological quantum field theories and commutative Frobenius algebras.

April 20

Topology Seminar
Kayla Neal, Boise State University
Tiling Theory

April 27

Khoi Le, Boise State University
Pseudoprime: Classical vs. Elliptic
For centuries, prime numbers have been among the most fascinating topic in mathematics. Not because the topic is easy but because it is difficult. Apparently, there is no pattern for prime numbers. We start with 2 (the only even prime number), then 3, 5, 7, 11, … While Euclid proved (c. 300 BC) that there are infinitely many prime numbers, the question of whether or not a given number is prime has been an interesting study of mathematics, particularly in Number Theory. In 1640, Pierre de Fermat showed that IF we know that a number is prime, THEN an interesting property, say P, is guaranteed. However, the converse is not true. That is, if we have the property P, then we may or may not know that a number in question is prime; in addition, if we can actually tell that the number in question is not prime, then they are called (Fermat) pseudoprime. In fact, Robert Carmichael provided explicit examples regarding exactly this fact; hence these are called Carmichael numbers.

From 1986 to 1993, several mathematicians studied a new method for primality testing using elliptic curve; hence, the name “elliptic curve primality testing.” However, whenever there is a primality testing, there are pseudoprimes related to it; thus, in this case we have: elliptic pseudoprimes.

Since this method has been among the quickest and mostly used method in primality testing, in this paper, we will briefly go over what an elliptic curve is as well as what an elliptic pseudoprime is. Then, we will dive into elliptic Carmichael numbers and how they are not as “nice” as the classical Carmichael numbers.

Fall 2017


Organized by Zach Teitler

August 25

Open problems & Planning

September 1

Topology Seminar
Jens Harlander, Boise State University
The Geometric Realization Problem

September 8

Scott Andrews, Boise State University
The $q,t$-Catalan numbers
The Catalan numbers $C_n$ enumerate many different combinatorial objects, including triangulations of an $(n+2)$-gon, 123-avoiding permutations, and Dyck paths. There are two $q$-analogues of the Catalan numbers, both of which turn out to be specializations of the more general $q,t$-Catalan numbers. In this talk I will introduce the Catalan numbers and the idea of a $q$-analogue of a number and I will define the $q,t$-Catalan numbers.

September 15

Topology Seminar
Uwe Kaiser, Boise State University
A Survey of the Volume Conjecture in Knot Theory

September 22

Zach Teitler, Boise State University
Recent* advances in Waring rank and apolarity

September 29

Topology Seminar
Jens Harlander, Boise State University
Groups, Homology, and Bias

October 6

Zach Teitler, Boise State University
High-rank and maximum-rank geometry

October 13

Aaron Bertram, University of Utah
The Tropical Nullstellensatz
The (weak) Hilbert Nullstellensatz states that if a system of polynomial equations in several variables has no complex solutions then the equation $1 = 0$ must be a combination of the polynomial equations in the system. In this talk, I will discuss a version of this theorem that holds when complex numbers are replaced with tropical numbers. This is joint work with Rob Easton.

October 20

Jonny Comes, College of Idaho
The Heisenberg category: diagram calculus for induction and restriction functors
In 2010 Khovanov introduced the so-called Heisenberg category H. Among other things, H provides a diagrammatic setting for calculations involving induction and restriction functors for the symmetric groups. This talk will be an introduction to the Heisenberg category following Brundan’s more recent treatment. I will start with an introduction to induction and restriction for the symmetric groups. In particular, I will describe a combinatorial interpretation of induction and restriction in terms of arrays of boxes known as Young diagrams. This will lead us to the so-called “Mackey decomposition” for the symmetric group. I will then explain Brundan’s definition of H and its connection to induction and restriction. If time permits, I will discuss Khovanov’s motivation or describe one of my current projects related to this stuff.

October 27

Topology Seminar
Kayla Neal, Boise State University
Geodesics in Link Complements

November 3

Cassandra Peterson, Boise State University
Statistics and climate change
Several recent developments in statistics are directly related to and used to evaluate climate change.

November 10

Topology Seminar
Michelle Pyles, Boise State University
An Introduction to the Cap Set Problem: the game SET and Tic-Tac-Toe

November 17

No seminar meeting

November 24

No seminar meeting (Thanksgiving holiday)

December 1

Marion Scheepers, Boise State University
Permutation sorting and abstract mathematics
In this talk we feature two basic permutation sorting operations that are hypothesized to act in the genome maintenance program of certain organisms. It turns out that these sorting operations are manifestations of more general mathematical structures in graph theory, linear algebra and topology. We briefly survey these connections.

December 8

TBA

Spring 2017


Time: Fridays, 3:00-3:50
Location: MB 139

Co-organized by Zach Teitler and Marion Scheepers

January 13

No meeting

January 20

Zach Teitler, Boise State University
Geometry of high rank loci
Matrix rank, tensor rank, and other related notions of rank are highly important throughout mathematics, statistics, and many areas of engineering and sciences. Elements of high rank can have surprising applications, for example to questions in computational complexity, yet high rank elements are usually exotic and in many cases the locus of high rank elements is poorly understood — in fact, it is not generally known whether the highest possible rank locus is empty, arbitrarily large, or somewhere in between. I will describe one of the first general studies of high rank loci, showing for example that they are nested and giving meaningful dimension bounds. This is joint work in preparation with Jaroslaw Buczynski, Kangjin Han, and Massimiliano Mella. This talk will not assume familiarity with generalized ranks or rank loci; these ideas will be explained and illustrated with examples.

January 27

Topology Seminar

February 3

Zach Teitler, Boise State University
Arrangement apolarity
I will present work in progress with Jaroslaw Buczynski, Stefan Tohaneanu (U. Idaho), and Alexander Woo (U. Idaho) on apolarity of hyperplane arrangements. A hyperplane arrangement is a finite set of codimension 1 linear subspaces; from an algebraic perspective, it just corresponds to a polynomial that can be factored into linear factors. We study interrelationships between the geometrical properties of the arrangement and algebraic properties of the factored polynomial. This talk will consider apolarity, which roughly corresponds to: describing and counting the derivatives of the polynomial, and determining which differential operators annihilate the polynomial — that is, what differential equations have the given polynomial as a solution. I will describe some results and ongoing work.

February 10

Topology Seminar

February 17

Jonny Comes
An analog of jellyfish partition categories for finite special linear groups
The partition category P(n) and the jellyfish partition category JP(n) model tensor representations for the symmetric group S_n and alternating group A_n respectively. Generalizing the construction of P(n), Knop introduced a monoidal category K(n,q) that models tensor representations for the finite general linear group GL(n,q). In this talk I will explain how to “add jellyfish” to Knop’s category, which produces a category JK(n,q) that models tensor representations for the finite special linear group SL(n,q).

February 24

Topology Seminar

March 3

Zach Teitler, Boise State University
Lefschetz properties, hyperplane arrangements, inclusion matrices
I will review a very pleasant classical combinatorial result of Gottlieb: Fix integers m, i, j. Let M be the matrix with rows indexed by the i-subsets of [m] and columns indexed by the j-subsets, with (I,J) entry 1 if I is a subset of J, otherwise 0. Then Gottlieb’s result is a computation of the rank of M, namely, that M has full rank. I will use this to show that apolar algebras of certain hyperplane arrangements have the Weak Lefschetz Property, which will be defined and explained in the talk.

March 10

Topology Seminar

March 17

No seminar meeting

March 31

No seminar meeting

April 7

Zach Teitler, Boise State University
The Gessel-Viennot theorem
“The aliens will destroy Earth unless we answer their three questions!” shouted the general. “First, given lattice points E, N, W, S on the east, north, west, and south sides of a rectangle, we have to find how many ways there are to draw lattice paths from W to N, and from S to E.”
“Oh, no problem,” said the secret agent. “I can solve that using binomial coefficients. You know, Pascal’s triangle.”
“You didn’t let me finish! The paths have to be disjoint. Once you pick one of the paths, it affects how many options there are for the other path.”
“Hmm. What were the other two questions?”
“Second, we have to find the area of a triangle in R^3. But we’re not given the vertices of the triangle — just the areas of its three projections onto the xy, xz, and yz planes. Third, we have to show that the matrix whose (i,j) entry is the binomial coefficient \binom{a_i}{b_j}, for fixed nonnegative integers a_1<…<a_n and b_1<…<b_n, has a nonnegative determinant which vanishes if and only if some a_i<b_i.”
“Well, is that all,” smirked the agent. “We’ll have these alien questions answered for you in no time. The Earth is as good as saved.”

The Gessel-Viennot theorem, 1985 (also due independently to Lindstrom, 1973 and Karlin-McGregor, 1959) relates determinants to nonintersecting path systems in graphs. Its numerous applications include counting nonintersecting lattice paths; a proof of the Cauchy-Binet formula, which in turn implies a generalization of Pythagoras’s theorem; and studying determinants of matrics of binomial coefficients. Other applications include showing different definitions of Schur polynomials are equivalent.

This talk will move quickly through a statement and a simple proof of the Gessel-Viennot theorem, and as many applications as we can fit into the time. Students will be able to follow the talk which will require only some familiarity with determinants and graphs.

Attend the seminar, learn some math, save the Earth from aliens!

April 14

Topology Seminar

April 21

TBA

April 28

TBA

Fall 2016


Fridays, 3:00-3:50
Location: MB 124

Co-organized by Zach Teitler and Marion Scheepers

September 9

Marion Scheepers, Boise State University
The parity of permutations and quadratic reciprocity
In this talk we explain a clever proof, discovered in the 1870’s by Zolotarev, of the quadratic reciprocity law for the integers. Zolotarev’s proof allows generalization to various other rings.
Slides

September 23

Samuel Coskey, Boise State University
The set splittability problem
The set splittability problem asks whether, given a collection of finite sets, there exists a single set that selects exactly half the elements from each set in the collection. If a set has odd size, we may select either the floor or the ceiling of half its elements. The question is naturally a part of combinatorial discrepancy theory, since a collection is splittable if and only if its discrepancy is at most 1. In this talk we will show that the set splittability problem is NP complete. On the other hand, we will give several partial solutions to the problem for small collections and other special collections. This work was completed during our REU program in collaboration with P. Bernstein, C. Bortner, S. Li, and C. Simpson.

October 7

Liljana Babinkostova, Boise State University
Anomalous Primes and the Elliptic Korselt Criterion
Although there now are polynomial time primality tests that correctly identify numbers as prime or composite, these tests run slower than tests that sometimes incorrectly classify certain composite numbers as prime.
The classical test based on Fermat’s Little Theorem is an example of this second class of tests. Carmichael numbers, described by Korselt before their discovery, are such composite numbers misclassified by Fermat’s Little Theorem-based test.
Primality tests based on elliptic curves were introduced in the 1980’s. Some of these tests, like the classical Fermat’s Little Theorem based tests, misclassify some composite numbers as prime. This gave rise to the notion of elliptic Carmichael numbers. Silverman formulated criteria for identifying these numbers, and called one class the Type I elliptic Korselt numbers. In this talk we define anomalous prime numbers and explain their connection to the Type I elliptic Korselt numbers, generalizing previous results. This is joint work with J. Bahr, Y. Kim, E. Neyman and G. Taylor.

October 21

Jonny Comes
Jellyfish Brauer and partition algebras
Let O(n) denote the group of orthogonal nxn matrices and V the vector space of length n column vectors. There is a natural action of O(n) on tensor powers of V. The corresponding centralizer algebra was described via stacking certain diagrams by Brauer in 1937. The resulting diagram algebras (now called Brauer algebras) have been a hot topic in representation theory over the past 30 years. In Brauer’s 1937 paper he also describes some additional diagrams in order to model the centralizer algebra for the action of the special orthogonal group SO(n). However, Brauer does not explain how to multiply these new diagrams. Instead, he writes “The rule for the multiplication . . . can also be formulated. It is, however, more complicated and shall not be given here.” These diagrams received little to no attention until 1999 when Grood finally formulates a multiplication algorithm. Grood’s algorithm is indeed complicated, involving many steps. Moreover, as Grood points out, her multiplication rule is not even associative!

In this talk I will describe an alternative method for drawing and multiplying Brauer’s diagrams related to SO(n). In some sense, my diagrams are obtained from Brauer’s by “adding jellyfish”. The resulting “Jellyfish Brauer algebra” turns out to be an associative quotient of Grood’s algebra. I will also describe “Jellyfish partition algebras” which model the centralizer algebras for the action of alternating groups.

November 4

Jason Smith, Boise State University
The Fibonacci Number of the Tadpole Graph
An independent set of vertices of a graph G contains only nonadjacent vertices. Since the number of independent sets of the path Pn is the Fibonacci number Fn+2, we call the number of independent sets of a graph G its Fibonacci Number. Since the Fibonacci Number of the cycle graph Cn is the Lucas number Ln, it is natural to look for other graphs whose Fibonacci Numbers form a Gibonacci sequence. The Fibonacci Numbers of Tadpole Graphs not only form a Gibonacci sequence but can also be organized into a symmetric Pascal-like triangle that has many combinatorial properties.

Spring 2016


Time: Fridays, 3:00-4:00pm
Location: MB 124

Co-organized by Zach Teitler and Marion Scheepers

January 15

Zach Teitler, Boise State University
Strassen’s additivity conjecture and bounds for Waring rank
The Waring rank of a complex homogeneous form is the least number of terms in an expression of the form as a sum of powers of linear forms. Waring rank, tensor rank, and various generalized ranks are interesting for a range of applications including secant varieties and geometric complexity theory, but they are difficult to compute. In particular we do not know the maximum Waring rank among forms in a given number of variables and a given degree; it is not even known whether forms of greater than generic rank exist. I will present upper and lower bounds for Waring rank and generalized ranks that narrow the possible ranges of maximum values of generalized ranks (joint work with Grigoriy Blekherman) and in some new cases show the existence of forms of above-generic Waring rank (joint work with Jaros{\l}aw Buczy\’nski). I will present a sufficient condition for forms to satisfy a strong form of Strassen’s additivity conjecture, which asserts that the Waring rank of a sum of forms in independent variables is the sum of their ranks.

January 22

Cancelled due to illness

January 29

Zach Teitler, Boise State University
Random graphs
Introduction to random graphs and overview; Crossing Lemma; application to combinatorial geometry.

February 5

Topology Seminar

February 12

Hirotachi Abo, University of Idaho
Eigenvectors of tensors
Eigenvectors of tensors were first introduced by L. Qi and L.-H. Lim independently in 2005. The set of eigenvectors of a tensor forms a variety called the eigenvariety of the tensor. The purpose of this talk is to study the algebra and geometry of eigenvarieties of tensors.
The eigenvariety of a general tensor consists of a finite number of eigenvectors (up to scaling) and the formula for counting the number of distinct eigenvectors of such a tensor is known. It is therefore a very natural question to ask: “What is the condition(s) for a finite set of points to be the eigenvariety of a tensor?’’ In this talk, I discuss a characterization of eigenvarieties of 3-mod ternary tensors.

February 19

Topology Seminar

February 26

Jason Smith, Boise State University
Using graphs to count
By counting triangles in complete graphs and edges in complete bipartite graphs we give combinatorial proofs for identities for sums of the first n positive integers, square integers, and cubed integers. An open problem will be given. Time permitting purely combinatorial proofs for these identities will also be given.

March 4

Marion Scheepers, Boise State University
Sorting Permutations
Sorting is often the first step in preparing data for processing by search and other algorithms. As such sorting algorithms have been studied extensively. In this talk we feature two specific sorting operations that have emerged as important to achieving efficiency in sorting.

March 11

TBA

March 18

TBA

March 25

No meeting due to Spring Break

April 1

Joe Champion, Boise State University
Integral Arithmagons
Arithmagons are informally presented in some school mathematics curricula as polygonal figures with integer labeled vertices and edges in which, under a binary operation, adjacent vertices equal the included edge. Though providing an interesting opportunity for a range of problem solving tasks, arithmagons have only recently been formally defined and characterized. By considering the group of automorphisms for the associated graph, we will count the number of integral arithmagons whose exterior sum or product equals a fixed number.

April 8

Topology Seminar

April 15

Ellen Veomett, St. Mary’s College of California
The Edge Isoperimetric Inequality for a Graph on Z^n
Isoperimetric inequalities raise very natural questions about the shape of a set and the resulting size of the boundary. The Euclidean isoperimetric inequality in the plane asks: given a closed loop, what shape should I make so that the loop encloses the largest possible area? We will discuss how the Brunn-Minkowski inequality can be used to prove the isoperimetric inequality in R^n. We will then discuss how one can define an isoperimetric inequality for a graph and give various examples of results on graphs. Interestingly, we can also use the Brunn-Minkowski inequality to solve a continuous formulation of the edge isoperimetric inequality for a graph on Z^n, which should in turn help us to solve the edge isoperimetric inequality on this graph.

April 22

Bruce Reznick, UIUC
Sums of powers of polynomials

April 29

TBA

Fall 2015


Fridays, 3:00-3:50
Location: MB 124

Co-organized by Zach Teitler and Marion Scheepers

August 28

Open Problems Discussion
An informal sharing and discussion of open problems. All seminar participants are encouraged to bring open problems and puzzles to share, especially recently learned ones.

September 4

Topology Seminar

September 18

Jonny Comes, College of Idaho
Tensors for general linear and orthosymplectic supergroups
Let V be an m-dimensional vector space and GL(m) the corresponding general linear group. A classical result of Schur explains how any tensor power of V decomposes as a direct sum of simple GL(m)-modules. In this talk I will explain what is known about the analogous decompositions when one allows mixed tensor powers (allowing powers of both V and its dual) and/or replaces the group GL(m) with the groups O(m), Sp(2n), or the supergroups GL(m|n), OSp(m|2n), or Q(n).

September 25

Zach Teitler, Boise State University
Waring rank bounds
The Waring rank of a homogeneous polynomial of degree d is the least number of terms required to write it as a sum of d’th powers of linear polynomials. I will review applications of Waring rank, focusing on complexity theory and interpolation, and I will give a brief general introduction to Waring rank. I will present a bound for Waring rank found by Carlini, Guo, and Ventura, along with some ideas for generalizations; I will describe some related possible research projects for students.

October 2

Zach Teitler, Boise State University
Experimentation at the Frontiers of Reality in Schubert Calculus
I will describe computational experiments on real solutions in Schubert Calculus.

October 9

Scott Andrews, Boise State University
The representation theory of finite unipotent groups
In this talk I will discuss the representation theory of UT(n,q), the group of unipotent upper-triangular matrices with entries in the finite field with q elements. Indexing the irreducible modules of UT(n,q) is known to be a ‘wild’ problem. By considering a collection of modules that are not irreducible, but behave like irreducible modules, one obtains a structure that contains rich combinatorial data. I will present this construction and talk about generalizations to symplectic, orthogonal, and unitary matrices.

October 16

No meeting

October 23

Zach Teitler, Boise State University
Strassen additivity conjecture
I will describe the Strassen additivity conjecture and a simple sufficient condition for it to hold.

October 30

No meeting

November 6

Zach Teitler, Boise State University
Forms of high rank
I will discuss recent progress and questions about homogeneous forms of high rank. Rank, in particular Waring rank, is a measure of complexity. The famous P vs. NP question in complexity theory has analogues in geometric complexity theory, including conjectures of Valiant and Mulmuley-Sohoni, which according to Strassen and Raz could be resolved by producing forms of sufficiently high rank. However it is not known how to produce such forms, or even if any forms of higher than generic rank exist at all.
In this talk I will explain all of the above—Waring rank, complexity, and the central question whether there even exist any forms of higher than generic rank. I will describe joint work with Grigoriy Blekherman that limits the potential scope for forms of higher than generic rank. I will sketch joint work with Jaroslaw Buczynski that shows in some cases the existence of forms of higher than generic rank.

November 13

Jonny Comes, College of Idaho
A q-analogue of the partition algebra
In this talk I will describe the partition algebra P_k(n) introduced by Martin in the early 1990s. Elements in P_k(n) are linear combinations of diagrams (representing set partitions) and multiplication is described in terms of stacking diagrams. I will explain how these algebras arise as centralizer algebras for the action of the symmetric group S_n on tensor powers of the natural representation of S_n. The goal of this talk is to describe a q-analogue of the partition algebra introduced by Knop in 2006. These algebras arise if one replaces S_n with the finite general linear group GL(n,q) and looks for the corresponding centralizer algebras.

November 20

Liljana Babinkostova, Boise State University
Grostl, Permutations and Transversals
Permutations are important building blocks for any cryptographic schema. In this talk we focus on the properties of permutations that dictate the security of some cryptographic hash functions. Furthermore, we present a nice analogy of the problem of existence of a “good” permutation to the problem of counting transversal in latin squares.

December 4

TBA

Spring 2015


Fridays, 3:00-3:50
Location: MB 139

April 24

Topology Seminar

April 17

Zach Teitler, Boise State University
The slope problem
What is the smallest possible number of slopes that can be generated by a set of n points in the plane, assuming the points are not collinear? If the points are randomly chosen then with probability 1 every pair of points generates a line with a different slope and the number of slopes is \binom{n}{2}, the largest possible number of slopes. To get a small number of slopes, roughly speaking, the points have to generate as many parallel lines as possible. For example, for n=4, the vertices of a parallelogram generate just 3 slopes instead of 6.

In 1970 Scott conjectured that a set of n points determines at least n-1 slopes if n is even, and at least n slopes if n is odd. We will present a beautiful proof of this discovered in 1981-1982 by Goodman and Pollack, and Ungar. The proof uses a sequence of permutations starting with (1,2,…,n) and ending with (n,…,2,1) where each step involves reversing an increasing subsequence.

This is remarkably similar to the structures that arise in studying ciliate DNA permutations; although it is not quite the same thing, I hope that it will be interesting to everyone working on that problem. (However I will not assume any knowledge of ciliate DNA permutations. The Goodman-Pollack-Ungar proof uses beautiful and simple ideas. This talk will have a lot of pictures!)

April 10

Topology Seminar

April 3

Jonny Comes, College of Idaho
The affine oriented Brauer category
An oriented Brauer diagram is a bunch of oriented strands connecting points at the top of a page with points at the bottom, possibly with crossings in between. These diagrams resemble oriented tangles, except that oriented Brauer diagrams do not distinguish between over and under crossings. Oriented Brauer diagrams together with the operations of vertical and horizontal stacking define the oriented Brauer category, OB. Roughly speaking, the affine oriented Brauer category, AOB, is obtained from OB by adding dots to stands and imposing a relation which explains how to pass these dots through crossings. I will explain how the definition of AOB is motivated by a connection between oriented Brauer diagrams and the general linear group. I will then state a basis theorem for AOB and give an outline for its proof. This is joint work with Brundan, Nash, and Reynolds (arXiv: 1404.6574).

March 6

Zach Teitler, Boise State University
Product Ranks of the 3×3 Determinant and Permanent
We consider ways of writing the determinant and permanent (the same thing as the determinant “without minus signs”) by adding together terms that can be factored into linear forms. For example, ordinary monomials can be factored, which leads to using 6 monomials each for the determinant and permanent. Recently expressions have been found with factorable terms other than monomials, using just 4 terms for the permanent and 5 for the determinant. I will show what these are, then explain the proof that Nathan Ilten and I found that these are the smallest possible expressions. This is joint work with Nathan Ilten posted recently, arXiv:1503.00822.

February 27

Zach Teitler, Boise State University
Using cotangent to find the sum of 1/n^{2k}
It is well known that the sum of 1/n^2 is equal to pi^2/6, but what about the sum of 1/n^4, 1/n^6, and so on? We will evaluate these sums using an amazing connection between the Riemann zeta function and Bernoulli numbers. The connection arises from the cotangent function, for which we will find a partial fraction decomposition just like in second-semester calculus. In this case the partial fraction decomposition is a conditionally convergent series. The key ingredient is “Herglotz’s trick”. In the end we will get a peek into the mind of Euler.

February 20

Zach Teitler, Boise State University
Monsky’s Theorem
Monsky’s Theorem asserts that if a square is cut into triangles of equal areas, then the number of triangles must be EVEN. The amazing proof involves ingredients from two areas of mathematics: combinatorial/topological and number theory/algebra. I will outline the ingredients, including Sperner’s Lemma, 2-adic valuations, and colorings of the plane.

February 13

Cancelled due to illness

February 6

Topology Seminar

January 30

Jonny Comes, College of Idaho
Brauer diagrams and representation theory
In this talk I will describe the role of Brauer diagrams in representation theory. I will start with a brief introduction to representation theory. In particular, I will explain how the representation theory of symmetric groups and general linear groups are intimately connected by what is known as Schur-Weyl duality. I will then discuss how Brauer diagrams arise in this setting if one replaces the general linear group with the orthogonal group and looks for a corresponding analogue to the symmetric group. If time permits, I will discuss one of my current research projects related to all of this stuff.

January 23

Topology Seminar

Fall 2014


Fridays, 2:30-3:30
Location: MB 136

Nov 21

Zach Teitler, Boise State University
Monsky’s Theorem
Monsky’s Theorem asserts that if a square is cut into triangles of equal areas, then the number of triangles must be EVEN. The amazing proof involves ingredients from two areas of mathematics: combinatorial/topological and number theory/algebra. I will outline the ingredients, including Sperner’s Lemma, 2-adic valuations, and colorings of the plane.

Nov 7

Jaroslaw Buczynski, IMPAN/University of Warsaw
Subvarieties and maps of affine spaces, projective spaces and toric varieties
The affine space is a set of tuples of complex numbers. The projective space is a set non-zero tuples of complex numbers, modulo an equivalence: two tuples are equivalent, if one is a multiple of the other. Thanks to these description we can talk about coordinates on the affine space or homogeneous coordinates on the projective space. A much wider class of geometric objects has sensible coordinates. In this class are toric varieties, which I will describe. Coordinates are useful to describe geometric subsets (of an affine space, a projective space, a toric variety). These geometric subsets are called subvarieties. Moreover, one often uses coordinates to describe maps between affine spaces, or projective spaces. I will present a method to use coordinates to describe maps between toric varieties.

Oct 24

Gregory G. Smith, Queen’s University
Cones of Hilbert functions
Hilbert functions are fundamental invariants in commutative algebra and algebraic geometry. After recalling the basic definitions and motivating examples, we will discuss new and old methods for characterizing the collection of all Hilbert functions. This talk is based on joint work with Mats Boij.

Oct 3

Zach Teitler, Boise State University
Bounding Hilbert functions of multiple point schemes
We give upper and lower bounds for the number of (i.e., dimension of the space of) curves passing through a given set of points with assigned multiplicities. This is joint work with Susan Cooper and Brian Harbourne.

Sept 26

Zach Teitler, Boise State University
The addition of residue classes modulo n (part 2)
I will finish my presentation of Ryavec’s elementary proof in 1968 of the following theorem. Let a_1,..,a_m be m distinct, nonzero residues modulo n, where n is any natural number and where m is greater than or equal to 3sqrt(6n)exp{c sqrt(log n) / log log n}, where c > 0 is some large constant. Then there is a nonempty subset of the a_i which sums to 0 modulo n. Note that the bound for m is O(n^(1/2+epsilon)) for all epsilon>0. This answers a question of Erdos.

Sept 12

Zach Teitler, Boise State University
The addition of residue classes modulo n
I will present Ryavec’s elementary proof in 1968 of the following theorem. Let a_1,..,a_m be m distinct, nonzero residues modulo n, where n is any natural number and where m is greater than or equal to 3sqrt(6n)exp{c sqrt(log n) / log log n}, where c > 0 is some large constant. Then there is a nonempty subset of the a_i which sums to 0 modulo n. Note that the bound for m is O(n^(1/2+epsilon)) for all epsilon>0. This answers a question of Erdos.

Sept 5

Zach Teitler, Boise State University
Lower bound for ranks of invariant forms
We give a lower bound for the Waring rank and cactus rank of forms that are invariant under an action of a connected algebraic group. We use this to improve the Ranestad–Schreyer–Shafiei lower bounds for the Waring ranks and cactus ranks of determinants of generic matrices, Pfaffians of generic skew-symmetric matrices, and determinants of generic symmetric matrices. This is joint work with Harm Derksen.

I will explain all terms appearing above so that it will be accessible for students.

Aug 29

Open Problem Discussion
An informal sharing and discussion of open problems. All seminar participants are encouraged to bring open problems and puzzles to share, especially recently learned ones.

Spring 2014


Tuesdays, 3:00-3:50
Location: MB 136

May 6

Zach Teitler, Boise State University
The proof of Tarski-Seidenberg
I will give a proof of the Tarski-Seidenberg theorem. This is the conclusion of “The Simple Tarski-Seidenberg Tutorial Series”. I will review the main ideas as needed, so you can catch up if you missed previous talks. (In particular this will not actually use any of the applications of the Tarski-Seidenberg theorem described in parts 3-6 of the tutorial series, so if you missed those, it will not affect comprehension of this talk.)

April 29

Zach Teitler, Boise State University
Two puzzles
I will present a puzzle and its solution. Then I will present another puzzle.
The first puzzle concerns stacking blocks and an algebraic identity. The second puzzle concerns determinants.

April 15

Zach Teitler, Boise State University
Determinants and permanents as sums of products of linear forms
I will present some very recent ideas on expressions for determinants and permanents as sums of products of linear forms, a consequence for Waring rank, and some questions.

March 18

Zach Teitler, Boise State University
Hilbert’s 17th problem
Continuation of “The Simple Tarski-Seidenberg Tutorial Series”.

March 11

Zach Teitler, Boise State University
Positivstellensatz
Continuation of “The Simple Tarski-Seidenberg Tutorial Series”.

March 4

Zach Teitler, Boise State University
Real Nullstellensatz
Continuation of “The Simple Tarski-Seidenberg Tutorial Series”.

February 25

Zach Teitler, Boise State University
Transfer theorems, Artin-Lang theorem
Continuation of “The Simple Tarski-Seidenberg Tutorial Series”.

February 18

Zach Teitler, Boise State University
Real fields and real closure
Continuation of “The Simple Tarski-Seidenberg Tutorial Series”.

February 11

Zach Teitler, Boise State University
Tarski-Seidenberg theorem and semialgebraic sets
Beginning of “The Simple Tarski-Seidenberg Tutorial Series”.

January 28

Zach Teitler, Boise State University
The sequence 1, 3, 16, 125, 1296…, two ways
The discriminant of the polynomial 1+x+…+x^{n-1} and the number of trees on n labeled vertices are both equal to n^{n-2}.

Fall 2013


Tuesdays, 3:00-3:50
Location: B204

December 10

Erik Holmes, Boise State University
Sorting permutations by the ciliate decryptome
Ciliates, single celled organisms, upgrade their genome by reordering the encrypted DNA of their micronuclei into readable strands. The decryption process uses context guided operations which can be modeled on permutations. It turns out that these operations are not always capable of completely ordering an arbitrary permutation α, which is one of the main motivations for the mathematical study of the ciliate decryptome.

In this talk we will briefly mention the biological background of the ciliate, but the main focus will be on one of the operations and its affect on permutations. We will begin by providing all necessary background information, after which we highlight the work done during the summer REU at Boise State, focusing on the characterization of CDS-invertible permutations. We conclude the talk with a discussion of an open question regarding permutation groups, for which we provide some partial results.

December 3

Zach Teitler, Boise State University
On Maximum, Generic, and Typical Ranks

I will present new bounds for maximum rank in terms of generic and typical ranks, valid for generalized rank. In the case of Waring rank these improve the previously best known bounds. This is joint work in preparation with Greg Blekherman.

November 12

David Albertson, Boise State University
Generalization of the Whirlpool Hash Function
In the fast-paced world of cryptography innovations, it is essential to anticipate attacks that will result in insecure electronic communication. Hash functions are used for password storage, message integrity verification, pseudorandom number generation, and non-repudiation in digital security. A hash function takes a string of arbitrary length and returns a string of a fixed length.

Whirlpool is a hash function developed in 2003 and accepted by the New European Schemes for Signatures, Integrity, and Encryption (NESSIE) for widespread use. Whirlpool uses a Rijndael-type block cipher in a Merkle-Damgård construction to create a hash function. This internal block cipher has a rich algebraic structure, which is vital to the security of the function.

We generalize the standard version of Whirlpool and explore these algebraic properties. In particular, we investigate the conditions under which the set of encryption functions used in Whirlpool form a group under functional composition. Our analysis of the component functions has diverse applications, especially in solving combinatorial problems from other areas, such as computer science and neuroscience.

November 5

Zach Teitler, Boise State University
Multiplier Ideals: From Integrals to Algebra
Multiplier ideals are defined in terms of convergence of improper integrals. I will explain how to study convergence or divergence of improper integrals using algebra.

October 29

Zach Teitler, Boise State University
Singularities and Multiplier Ideals
I will introduce multiplier ideals, which are an invariant of singularities; describe an application of multiplier ideals to boundedness of symbolic powers; and state some open problems ranging from computational challenges to theoretical investigations, many of which would be good for student projects.

The application to symbolic powers concerns the following amazing theorem. Say Z is a finite set of points in the plane, given as the solution set of polynomial equations F_1=F_2=…=F_n=0. If G can be written as a combination of products of m of the F_i’s, then — by the Product Rule for derivatives — G along with every partial derivative up to (m-1)’th order vanishes at every point of Z. But the converse does not hold: vanishing of partial derivatives does not imply G can be decomposed in this way. A priori, it is not at all clear that there is any r=r(m) such that assuming the partial derivatives up to (r-1)’th order vanishes will be enough to imply G is a combination of m-fold products of F_i’s. Astonishingly, Ein-Lazarsfeld-Mustata showed that simply r=2m works. (And more generally on a d-dimensional variety, r=dm works.)

The required prerequisite for this talk is to remember what an improper integral is. I will mention ideals too but for most of the talk they are nothing more than sets.

October 22

Marion Scheepers, Boise State University
Rearrangements of conditionally convergent series of real numbers
Early studies on the rearrangement of numerical series culminated in Riemann’s rearrangement theorem: If a series is convergent, but not absolutely convergent, then for any real number x a rearrangement can be found so that the rearranged series has sum x. One may ask if there is for each such x a quantity determined by x that informs one on how to rearrange the terms of the series to achieve sum x. In this talk we explain one approach to this question.

October 8

Zach Teitler, Boise State University
Maximum ranks of monomials, continued
The maximum Waring rank, for a given degree and number of variables, is unknown except in some small cases. It is not known whether the currently best upper bounds are close to the maximum or not. It would be helpful to have examples of high-rank forms, to provide lower bounds for the maximum — but very few examples of high-rank forms are known. I will discuss high-rank monomials.

In last week’s talk I presented context and motivation, ending by stating a theorem about high-rank monomials and a conjecture about sums of pairwise coprime monomials. In this talk I will prove the theorem and give evidence for the conjecture. I will describe what steps might lead to a proof of the conjecture, with the hope that it will be solved by students.

This talk can be understood independently of last week’s talk (although the motivation might not be obvious).

October 1

Zach Teitler, Boise State University
Maximum ranks of monomials
The maximum Waring rank, for a given degree and number of variables, is unknown except in some small cases. It is not known whether the currently best upper bounds are close to the maximum or not. It would be helpful to have examples of high-rank forms, to provide lower bounds for the maximum — but very few examples of high-rank forms are known. I will discuss high-rank monomials.

September 17

Zach Teitler, Boise State University
Recent advances in Waring rank and apolarity
Waring rank is a measure of complexity of polynomials related to sums-of-powers expressions and to a number of applications such as interpolation problems, blind source separation problems in signal processing, mixture models in statistics, and more. We review some recent advances having in common the use of apolarity, a sort of reversed version of differential equations in which one considers the set of differential equations that have a given function as a solution.

  1. Apolarity is applied to describe criteria for a polynomial to be expressible as a sum of functions in separate sets of variables, possibly after a change of coordinates. This is related to separation-of-variables techniques in differential equations and to topology (criteria for a manifold to be decomposable as a connected sum). This is joint work with Buczynska, Buczynski, and Kleppe.
  2. The set of sum-of-powers decompositions of a monomial is described. A corollary is a necessary and sufficient condition for a monomial to have a unique such decomposition, up to scaling the variables. This is joint work with Buczynska and Buczynski.
  3. One generalization of monomials is the family of polynomials that completely factor as products of linear factors, geometrically defining a union of hyperplanes. Waring ranks of hyperplane arrangements are determined in the case of mirror arrangements of finite reflection groups satisfying a technical hypothesis which includes many cases of interest. This is joint work with Woo.

If time permits, ongoing work will be described, including geometric lower bounds for generalized Waring rank, apolarity of general hyperplane arrangements, and a number of other open questions.

September 10

No meeting this week.

Spring 2013


Time: 1:30 p.m. – 2:30 p.m.
Location: B 102B

January 29

Zach Teitler, Boise State University
Symbolic vs ordinary powers

If a function is a product of N functions that each vanish on a set, then it vanishes to order N on the set, meaning that the function and its first N-1 derivatives vanish at each point in the set. But the converse does not hold: vanishing to order N does not imply factorizability, not even expressability as a sum of factorizable terms.

Unexpectedly, such expressability is indeed implied by high enough order of vanishing, according to a theorem of Ein-Lazarsfeld-Smith and Hochster-Huneke about symbolic versus ordinary powers of ideals. An “elementary” proof of this theorem is still not known, except in some (important, but still special) cases. New conjectures by Harbourne-Huneke propose even stronger comparisons. I will explain the theorem and conjectures, hint at the modern techniques involved in the general proofs, and say why they might not be good enough for the stronger conjectures.

February 26

Zach Teitler, Boise State University
Powers of elements and monomial ideals

I will present work of Reinhold Hübl that appeared in Comm. Alg. in 2005 as “Powers of elements and monomial ideals”.

An ideal I in a local ring (R,m) is said to have property NN if f is in mI whenever f is in I and f^n is in I^{n+1} for some n. It is an open question whether all radical ideals in regular local rings have this property. This question was studied by Eisenbud and Mazur, among others, in connection with the proof of Fermat’s Last Theorem.

In this paper Hübl characterizes monomial ideals with property NN, in terms of the Newton polyhedron.

March 12:

Jason Smith, Boise State University
Introducing the p-adic Numbers
The field of p-adic numbers was first introduced by Hensel around 1900. This field has many surprising properties that continue to fascinate the mathematical world.

Quoting Kato et al, “It is as if those who had seen the sky only during the day are [now] marvelling at the night sky. The mathematical scenery is completely different. Qp emits the light of a prime number p in the night sky as if it were a star that we could not see because of the sun, or the real number field R, which emits the light of the real numbers during the day.”

This talk will consist of two Lectures:

  • Lecture 1: Define the p-adic number field and give some basic properties.
  • Lecture 2: Prove Hensel’s Lemma and then use this to perform the Hensel Lift to factor some polynomials in Z[x].

April 2

Dillon Wardwell, Boise State University
An Application Of Graph Theory To Algebra
In this talk we will present an application of graph theory to commutative algebra. Amitsur and Levitzki proved in 1949 that n-by-n matrices with entries from a commutative ring satisfy a generalized commutator identity: if A_1,…,A_{2n} are n-by-n matrices with entries from a commutative ring then the signed sum of the permuted products of the A_i is zero. We will explain the Amitsur-Levitzki identity and present Richard Swan’s 1962 graph theoretic proof of the same identity, using Euler paths. An advantage to this approach is that complicated algebraic definitions can be interpreted as simpler geometric ones by drawing a picture of an appropriate graph.

April 16

Zach Teitler, Boise State University
How Many Curves?
How many curves go through a given set of points, with given multiplicities? This is related to interpolation—a function specified by giving values and derivatives at several points is determined only up to terms whose values and derivatives vanish at those points, i.e., curves vanishing at the points with given multiplicities. The question of the title thus amounts to asking for the indeterminacy of an interpolation problem. It is also related to a number of other problems in algebra and geometry.

I will present joint work with Susan Cooper and Brian Harbourne that gives upper and lower bounds for the number of curves, and conditions for the bounds to coincide, with especially good results when there are collinearities among the points. I will emphasize the role of cohomology (homology’s cousin) and exact sequences as tools within algebra and geometry (not only good for topology!), without assuming the audience is familiar with cohomology or exact sequences (all needed ideas will be explained).

April 30

Zach Teitler, Boise State University
Apolarity and reflection groups
I will present the new paper “Apolarity and reflection groups”, written with Alex Woo, available at http://arxiv.org/abs/1304.7202.

We determine the Waring rank of the fundamental skew invariant of any complex reflection group whose highest degree is a regular number. This includes all real reflection groups.

I will explain (1) what is Waring rank and how it is linked to interpolation and other problems, (2) what is a reflection group and enough invariant theory to understand the theorem, (3) some open problems.

Fall 2012


Time: 3:00 p.m. – 4:00 p.m.
Location: room MG 139

September 4

Zach Teitler, Boise State University
Open problems discussion
I will present some open problems; seminar participants are encouraged to share as well, especially new problems they have learned recently.

September 18

Zach Teitler, Boise State University
Apolarity and Waring’s problem
Waring’s problem asks to write a given polynomial as a sum of powers. The main tool to address this is apolarity. I will introduce apolarity and sketch connections with the theory of partial differential equations and with geometry. I will describe some current (ongoing) research on properties of apolar ideals.

October 2

Kameryn Williams, Boise State University
Maximal unbalanced families
A family of subsets of an n element set is unbalanced if the convex hull of its characteristic vectors misses the diagonal in the n-cube. Such a family is maximal if every proper superset is balanced. I will present results on the upper and lower bounds for the number of maximal unbalanced families over an n element set. Both bounds are of the form 2^{C n^2}, for some C > 0. In particular, the proof for the upper bound is obtained via the geometry of the collection of all maximal unbalanced families for some n. Additionally I will present some results on the automorphisms of this collection and conjecture that the only automorphisms correspond to complementations or permutations on the n element set. The paper is available at http://arxiv.org/abs/1209.2309.

October 16

Marion Scheepers, Boise State University
The computational capabilities of the ciliate decryptome
An ancient group of organisms, named ciliates, routinely do sophisticated computations to reconstruct a functional nucleus from an encrypted version. We call the cellular machinary that perform these computations the ciliate decryptome. The decryptome is programmable, and the results of intermediate steps of these computations can be accessed.

In this talk I will describe how the ciliate decryptome performs certain group theoretic operations, and give an application of ciliate operations to phylogenetics. Several undergraduate students are involved in this work through REU projects, INBRE projects or independent research arrangements. Time permitting, I will indicate some research opportunities for students.

October 30

Liljana Babinkostova, Boise State University
Generalizations and algebraic structure of DES and AES
Blockciphers are a central tool in symmetric key cryptography. The Data Encryption Standard (DES) and the Advanced Encryption Standard (AES) are block ciphers approved by the U.S. Government as standards for encrypting digital information, including financial, telecommunications, and government data. In particular, they have been incorporated into numerous other standards, such as the American Bankers Association’s Protection of PIN’s in Interchange Standard, the Standard for Personal Identification Number (PIN) Management and Security, and the Standard for Financial Institution Message Authentication. They are also approved algorithms in the IP Security Architecture (IPSec) standard. Although the AES and DES are closely related in terms of their underlying design philosophies, their mathematical structure is quite different. Investigating the algebraic structure of a block cipher is of interest cryptographically. It can identify and exclude undesirable properties that could make the block cipher weak against certain attacks. In this talk we present generalizations of AES and DES, and discuss aspects of their algebraic structure that could lead to improving their security, particularly the security of AES. This is collaborative work with several undergraduate students.

November 13

Zach Teitler, Boise State University
Some questions about power sum decompositions
A power sum decomposition of a polynomial is an expression of that polynomial as a linear combination of powers of degree-1 polynomials. For example XY = (1/4)(X+Y)^2 – (1/4)(X-Y)^2, a linear combination of two squares. I will discuss a number of questions about power sum decompositions.

November 27

Liljana Babinkostova, Boise State University
Elliptic Reciprocity
Elliptic Curves are well-known mathematical objects described by Diophantine equations of the form y^2 = x^3 + ax + b. Elliptic curves of prime order are particularly well-suited for public-key cryptographic applications. We define and examine the notion of an elliptic pair and use it to formulate elliptic reciprocity. We also introduce the notion of elliptic lists and elliptic cycles and prove some results limiting both. These results are then used to find the smallest elliptic cycle of length 6. Several properties of proper elliptic lists will be presented that can be used to address the question whether or not proper elliptic lists of arbitrarily large length exist. Finally, we address the question of the distribution of elliptic pairs and how it is related to some old conjectures about quadratic polynomials.

December 11

TBD

Spring 2012


Time: Wednesdays, 2:40 p.m. – 3:30 p.m.
Location: Room MG 124

January 25

Zach Teitler
Waring decompositions of monomials
A Waring decomposition of a polynomial is an expression of the polynomial as a sum of powers of linear forms, where the number of summands is minimal possible. In this talk, I will describe joint work with Weronika and Jarek Buczynski which proves that any Waring decomposition of a monomial is obtained from a complete intersection ideal, and determines the dimension of the set of Waring decompositions. (All these terms will be explained in the talk.) In addition I will describe a number of open questions, some (or all?) of which could be research projects for a student.

February 8

Meeting cancelled

March 7

Hirotachi Abo, University of Idaho
Ideals, varieties, and vector bundles
The area of mathematics that I work in is algebraic geometry. At its most basic, algebraic geometry is the study of the common zero loci of systems of polynomial equations. Such systems arise very naturally throughout mathematics, theoretical physics, mathematical biology, statistics, computer science and engineering. These objects considered geometrically are called varieties. The first goal of this talk is to discuss one of the guiding problems in algebraic geometry called Hartshorne’s conjecture, which asserts that every non-singular variety $X$ in projective $n$-space $\mathbb{P}^n$ should be a complete intersection if the codimension of $X$, i.e., $n-\dim X$, is small compared with $n$. The second goal is to explore the connection between the question whether varieties of small codimension of $\mathbb{P}^n$ are complete intersections and the question whether there are so-called indecomposable vector bundles of small rank on $\mathbb{P}^n$. If time permits, I would like to discuss how this talk is related to the talk I will give at the colloquium.

March 19

Zach Teitler
Decompositions of determinantal ideals
Let X be a 2-by-3 matrix whose entries are variables. Then X has three maximal (2-by-2) minors, each obtained by deleting one of the columns of X. It is well-known that the ideal generated by all three of the maximal minors is a prime ideal; its vanishing locus is the set of rank 1 matrices. The ideal generated by a single one of the minors is also a prime ideal. What about the ideal generated by two of the minors? More generally, what is the primary decomposition of an ideal generated by a subset S of the minors of a generic m-by-n matrix? Theorem: Under suitable hypotheses, this ideal is the intersection of two prime ideals, first the ideal generated by all the maximal minors of the matrix, second the ideal generated by the maximal minors of the set of columns that appear in all the minors included in S.
As motivation, the Hilbert-Burch theorem asserts that any finite set of points in the plane is defined by a system of equations given by the maximal minors of a generic k-by-(k+1) matrix whose entries are polynomials. Taking a subset of the minors corresponds to solving a subsystem of the system of defining equations of the point set. Our decomposition result yields some situations in which some of the defining equations are redundant.

If time permits I’ll mention some questions that remain open (as far as I know): deal with special matrices (symmetric, skew-symmetric, etc); deal with special choices of minors (e.g., adjacent minors); work out other properties of these ideals (e.g., free resolution).

April 25

Jason Smith, College of Western Idaho
Some Interesting Infinite Sums
Smith infinite sums abstract

Fall 2011


Time: Wednesdays 3:50 p.m. – 5:00 p.m.
Location: Room ILC 404

September 14

Zach Teitler

September 28

Kameryn Williams
DES Over Finite Groups
The security of cryptosystems is related to their algebraic properties. DES (Data Encryption Standard) is a block cipher over Z_2 which is known to not form a group under composition. The current methods to prove this are computationally intensive. We generalize DES over new groups and give a mathematical proof that this generalized DES is not a group.

October 12

Zach Teitler
Two independently discovered solutions to Waring’s problem for monomials within the last week
Every natural number is the sum of at most 4 squares, at most 9 cubes, 19 fourth powers, 37 fifth powers… For every n, there exists a g=g(n) such that every number is the sum of at most g n’th powers. This was a question asked by Edward Waring in 1770. The existence of g(n) was established only in the 1940’s; it is still an open question what is g(n), and in fact the value g(5)=37 was only proved in 1964 and g(4)=19 was only proved in 1986. I will discuss a variant of the problem which considers polynomials and asks, for a given polynomial, when it is written as a sum of powers, how many terms are needed? For example, xy can be written as a linear combination of two squares, xyz can be written as a linear combination of four cubes, and x^2y-y^2z can be written as a linear combination of five cubes. There are surprising applications of this problem throughout mathematics (including Hilbert’s work on the original Waring’s problem), statistics, and engineering. Despite the algebraic nature of the problem, a number of recent breakthroughs have come from geometric techniques. Within the last week (!) two groups working independently have found solutions to Waring’s problem for monomials — Carlini, Catalisano, and Geramita, and independently, W. and J. Buczynski and myself. I will discuss the current state of the art for Waring’s problem, sketch the newly discovered solutions for monomials, and list some of the many questions that are still open. This will be an elementary talk which will be accessible to undergraduates.

October 26

Liljana Babinkostova
Continued fractions and prime numbers
We discuss results by P. Erdos and K. Mahler about some arithmetical properties of the convergents of a continued fraction. Namely, they proved that for almost all numbers the greatest prime factor of the denominator of the n-th convergent A_n/B_n of an infinite continued fraction increases rapidly with n. This result leads to other interesting properties of continued fractions.

November 2

Liljana Babinkostova
Continued fractions and prime numbers (part 2)
Continuation of previous talk.

November 30

Marion Scheepers
Information Security and a game on groups
The objectives of information security departments are sometimes at odds with the objectives of customer care departments. Whereas the customer care department may want user friendly software for online transactions by customers, information security departments may want to restrict the level of user friendliness of the same software to prevent exploits that may compromise the security of the system. We describe an example discovered by Bleichenbacher in the late 1990’s. We model the particular exploit as a game played on a group by two persons. The talk will be accessible to undergraduate students with a modest exposure to elementary group theory.

December 7

Zach Teitler
Toric varieties

A toric variety is an algebraic variety with a group action by a torus. They have interesting geometric and topological properties, and arise in many situations in algebraic geometry. Apart from their naturalness, one reason to study toric varieties is that they have a beautiful combinatorial classification, which allows one to reduce many geometric questions to combinatorics — and conversely, geometric tools can be applied to combinatorial problems. For example, toric codes have been studied, generalizing Reed-Solomon and Goppa codes. In this talk, I will describe toric surfaces and explain how the resolution of singularities can be found using lattice combinatorics, which in turn reduces to a familiar friend, continued fractions.

Spring 2011


Time: Wednesdays, 2:40 p.m. – 3:30 p.m.
Location: Room MG 120

January 28

Jim Wolper, Idaho State University
The Information Theoretic Schottky Problem

February 9

Liljana Babinkostova

February 23

Liljana Babinkostova
Hasse’s theorem and its use in Cryptography
The security of several cryptosystems, digital signatures and key exchange protocols is based on the difficulty of solving the discrete log problem. Determining the order of the group that is used in these cryptographic algorithms turn out to be very important for their security. Hasse’s theorem gives bounds for the group of points on an elliptic curve over finite field and it is used in many methods for determining the order of the group. In this talk we give a proof of Hasse’s theorem and discuss how it is used in cryptography.

March 1

Nick Davidson
Modules over Localized Group Rings
In 1964, Paul Cohn proved that if F is a finitely generated free group, and Q is a field, then all ideals in the group ring Q[F] are free as Q[F]-modules. This implies that all finitely-generated submodules of free Q[F]-modules are free. In 1990, Cynthia Hog-Angeloni reproved Cohn’s result using techniques from geometric group theory. In this talk, we introduce the crossed product D*G, which generalizes the notion of a group ring. Then, leaning on Hog-Angeloni’s arguments, we prove that all finitely-generated submodules of free D*F-modules are free, where D*F is a crossed product of a division ring D with F. This generalized version of Cohn’s theorem can be used in the study of group rings Q[G], where G is not free. Let G be a semi-direct product H x F, where F is finitely generated and free. If Q[G] can be localized at the subgroup ring Q[H], then the localized group ring can be viewed as a crossed product D*F, then all ideals in the localized group ring of G are free.

March 9

Jason Smith
A proof that X^3 + Y^3 = Z^3 has no solutions in positive integers
pdf

March 16

Jason Smith
A proof that X^3 + Y^3 = Z^3 has no solutions in positive integers (part 2)
pdf

April 13

Zach Teitler
Introduction to topos theory

  • What is a topos? This will involve category theory. I will follow notes by Leinster, http://arxiv.org/abs/1012.5647v2.
  • How has topos theory been useful in geometry?
  • How has topos theory been useful in logic?

April 20

Uwe Kaiser
What is topological quantum computing?
I will describe some features and differences between classical and quantum computing. Then I will try to explain why unitary representations of braid groups (and with it 3-dimensional quantum topology) are an important topic in developing a realistic concept of a quantum computer.

May 4

Zach Teitler
Introduction to topos theory (part 2)
The last time I spoke, I gave an informal introduction to toposes, which were described as a tool for generalizing set theory. This time, I’ll sketch out definition of a sheaf, and try to justify sheaves as tools for generalizing geometry. The idea is to first replace a space by its collection of open sets, then replace a collection of open sets with a category. The sheaves on this category represent geometry in the sense that sheaves on the original space represented geometry on that space.

Fall 2010


Time: Fridays, 2:40 p.m. – 3:30 p.m.
Location: Room MG 124

September 3

Shari Ultman
The conjugacy problem in Artin’s braid group

September 10

Shari Ultman
The conjugacy problem in Artin’s braid group (part 2)

September 17

Zach Teitler
Exploring Conjectures in Real Schubert Calculus
How many lines in 3-space meet four given general lines? There are two, as long as we are working over an algebraically closed field such as the complex numbers. Schubert calculus addresses a family of similar problems involving arrangements of linear subspaces with prescribed intersections, again working over a closed field. Working over the real numbers, the Shapiro Conjecture gives a condition for all the solutions to be real. Early experimental computations attracted interest to the conjecture, which has spurred a great deal of activity in the last 15 years including theorems revealing new links between algebraic geometry and other areas, and new conjectures. I will describe a massive, ongoing computational experiment testing variants of the Shapiro Conjecture and revealing new phenomena. This will be an overview talk. No background in algebraic geometry is assumed.

September 24

Zach Teitler
Combinatorial bounds on Hilbert functions of points in the plane with multiplicities
Given $n$ arbitrary values at distinct points on the line, there is a unique polynomial of degree $n-1$ taking those values at those points — this simple interpolation problem can be solved by Lagrange interpolators. One generalization is to consider points in more than one dimension, where it is less trivial to construct an interpolator, but the questions of existence and uniqueness are still not hard. A further generalization is to specify not only values at these points, but also values of derivatives of the polynomial at those points, in other words a Taylor polynomial at each point. Now even the questions of existence and uniqueness are quite challenging. One natural question is to ask for the dimension of the space of interpolants of each degree. This sequence of dimensions is called the Hilbert function of that set of points, and it is a central problem in algebraic geometry and commutative algebra to understand and compute Hilbert functions. I will discuss some pleasingly elementary and combinatorial upper and lower bounds on Hilbert functions, i.e., the dimension of the space of interpolants — bounds which coincide surprisingly often, including some interesting cases in which these dimensions were not known. This is joint work with Susan Cooper and Brian Harbourne.

October 8

Jason Smith

October 15

Jason Smith

October 22

Liljana Babinkostova
Cryptography and Continued Fractions
Cryptosystems are used for providing privacy and ensuring authenticity of digital data. For several cryptosystems the integrity in providing these services is based on the difficulty of factoring certain large integers. In this talk I will discuss the roll of continued fractions in attempts to factor these integers. The basic ideas underlying the continued fraction method are also the foundation for most modern efficient factoring methods.

October 29

Zach Teitler
Introduction to elliptic curves, part 1

November 12

J. Scott Carter, U. South Alabama
Quandle Categorification
Recently, much mathematical activity has been spent in defining various categorifications of standard structures. In the most broad sense, to categorify means to replace a notion of equality with a notion of natural equivalence. It can also mean to promote an idea that you believe is natural in the category of sets to an alternative category for example to the category of categories. Starting from the notions of groups and quandles, I will define what is meant by the notion of a category in the category of groups or a category in the category of quandles. In both cases, I will give several examples, and relate these ideas to ideas in knot theory.

November 19

Zach Teitler
Projective plane and projective curves

December 3

Nathan Geer, Utah State University
An introduction to Topological Quantum Field Theory
In this talk I will give Atiyah’s axioms of a TQFT and then prove that Frobenius algebras are one to one correspondence with 1+1 TQFT’s.

December 10

Zach Teitler
We will complete our journey toward knowing the topology of nonsingular algebraic plane curves, by proving the formula we have seen for the genus of a curve in terms of its degree. I will describe the Riemann-Hurwitz formula for genus of a branched cover of Riemann surfaces — including a description of what is a branched cover of Riemann surfaces. Note to students: This seminar talk will describe an application of triangulations and Euler characteristic, building on material that has recently been covered in Jens Harlander’s topology class. And we will also talk about coverings, previewing material that will be a theme in the class next semester.

Fall 2009 Cryptology Seminar


Tuesdays in the Math/Geo building, room 120, 2:40 – 3:30

September 11

Organizational meeting

September 18

Group discussion about the complexity of the conjugacy problem

September 25

Jens Harlander
Different representations of elements of Sn to the same element of Bn

October 2

Jens Harlander
Lifting from Sn to Bn

October 9

Marion Scheepers
Further remarks about NP-completeness

October 16

Marion Scheepers
The knap-sack problem and Cryptography

November 6

Jens Harlander
Computational problems: Decision problems and Search problems

October 23

Jens Harlander
Generic case complexity of algorithms and problems

November 13

Jens Harlander
Complexity of the Post Correspondence Problem

November 20

Jens Harlander
Complexity of the 3-Satisfiability problem

December 4

Jens Harlander
Complexity of the Halting problem

Fall 2008 Cryptology Seminar


The interdisciplinary seminar of the cryptography and topology group on Group-based Cryptography will be meeting in the Spring 2009 on Wednesdays 3:40pm – 4:30pm in room MG 139. Pdf copies of relevant chapters from the book will be distributed by email.

We will read the book by Alexei Myasnikov, Vladimir Shpilrain and Alexander Ushakov Group based cryptography. The first fifty pages of the book can be seen at Manuscript.

Here is the thesis by Elie Feder Algorithmic Problems in the Braid Group from 2003.

A great webpage on Cryptography and Braids [ed: archived], and a Survey Decision Problems for Groups. For the CDP/CSP in Garside groups the papers of Volker Gebhardt The cyclic sliding operation in Garside groups and Solving the conjuagcy problem in Garside groups by cyclic sliding, and the papers by Birman/Gebhardt/Gonzlez-Meneses Conjugacy in Garside Groups I: Cyclings, Powers and Rigidity,
Conjugacy in Garside Groups II: Structure of the Ultra Summit Set , and Conjugacy in Garside Groups III: Peridic braids will be used. The paper by Elrifai and Morton Algorithms for positive braids is important for the understanding of the conjugacy problem in Garside groups.

January 28

Liljana Babinkostova
Diffie–Hellman key exchange and the group conjugacy problem

February 4

Liljana Babinkostova
Reduction of the decomposition search problem to the conjugacy search problem

February 11

Liljana Babinkostova
Word versus conjugacy problem

February 18

Liljana Babinkostova
The Anshel–Anshel–Goldfeld key exchange protocol

February 25

Uwe Kaiser
CDP/CSP in Garside groups I

March 4

Uwe Kaiser
CDP/CSP in Garside groups II

March 11

no seminar

March 18

Uwe Kaiser
CDP/CSP in Garside groups III

April 1

Uwe Kaiser
CDP/CSP in Garside groups IV

April 8

Jens Harlander
Generalized Artin groups I

April 15

Jens Harlander
Generalized Artin groups II

April 22

Marion Scheepers
What it means to be difficult I

April 29

Marion Scheepers
What it means to be difficult II

May 6

Marion Scheepers
The proof of Cook’s theorem