This site will look much better in a browser that supports web standards, but it is accessible to any browser or Internet device.

Skip Navigation skip menu and banner
University of Wyoming

UW Mathematics Department Algebra, Combinatorics & Number Theory Seminar

 

Fall 2007
 
Jan 28
3:10-4
RH 339		 Bryan Shader, University of Wyoming Mathematics Department Head
 
 

Abstract: Some open problems on (0,1) and (-1,1) matrices arising from the theory of communication complexity.  The talk will be self-contained, and all are welcome to attend.
Dec 3
3:10-4
RH 308		 Tyler Branyan, University of Wyoming Student
Equivalence Classes Created by the Affine Cipher
 

Abstract: The Affine Cipher is an early form of encryption that makes use of modular algebra. Analysis of the encryption of various messages led to observation that the Affine Cipher can define an equivalence relation on the set of all possible letter combinations. Knowledge of this allows for new methods of cryptanalysis of Affine Ciphers, eliminating the need for tedious frequency analysis which was previously used. While the Affine Cipher is not in use today, this example can be useful as in instruction tool for both equivalence relations as well as modular arithmetic. It also allows for new thinking on more modern problems which use modular algebra as a basis for encryption.

Nov 12
3:10-4
RH 308		 Renate Scheidler, Centre for Information Security and Crytography, University of Calgary (Canada)
Construction of Hyperelliptic Function fields of High Three-Rank
 

Abstract: A hyperelliptic function field is a field of the form k(x,y) where k is a finite field of odd characteristic and y^2 = D(x) with D(x) a square-free polynomial with coefficients in k. If D has even degree, or if D has odd degree and the leading coefficient of D is a non-square in k, then the Jacobian of the hyperelliptic curve y^2 = D(x) is essentially isomorphic to the ideal class group of the ring k[x,y].

This is the finite Abelian group of fractional ideals of k[x,y] modulo principal fractional ideals. Although generically, the 3-Sylow subgroup of this ideal class group is small (and frequently trivial), it is possible to generate hyperelliptic function fields -- even infinite families of such fields -- whose 3-rank is unusually large.

This talk presents several methods for explictly constructing hyperelliptic function fields of high 3-rank, and more generally, high l-rank for any prime l coprime to the characteristic of k. Some of these techniques are adapted from constructions originally proposed for quadratic number fields by Shanks, Craig, and Diaz y Diaz, while others are specific to the function field setting. In particular, we explore how extending the field of constants k can lead to an increase in the 3-rank of the hyperelliptic function field.

This is joint work with Mark Bauer and Mike Jacobson, both of the University of Calgary, and Yoonjin Lee of Ewha Women's University in Seoul, South Korea.

Nov 5
3:10-4
RH 308		 Sylvia Hobart
Perfect matchings, eigenvalue interlacing, and the Laplacian matrix.
 

Abstract: A perfect matching in a graph is a ser of disjoint edges which includes every vertex. In 1947, Tutte gave a combinatorial characterization of graphs which have a perfect matching.

This result, together with eigenvalue interlacing, can be used to find a necessary condition for a perfect matching in terms of the eigenvalues of the Laplacian matrix of the graph. The Laplacian matrix is almost the adjacency matrix; the diagonal entries give the degree of a vertex, and off-diagonal entries are 1 for an edge and 0 for a non-edge.

The talk is based on a 2005 paper by A. E. Brouwer and W. H. Haemers. No previous knowledge of Laplacian matrices, matchings, or interlacing will be assumed.

Oct 29
3:10-4
RH 308		 Bryan Shader
Think Positively (or at least non-negatively).
 

Abstract: This talk will present a characterization of those sign patterns that allow a nonnegative left-inverse, and will be self-contained and accessible to graduate students.

Oct 15
3:10-4
RH 308		 Arsen Elkin
Very simple modules and their applications to abelian varieties
 

Abstract: We will explore very simple representations (as defined by Yuri Zarhin) and discuss their use in computing endomorphism algebras of abelian varieties. Specifically, we will show how in some cases these computations can be reduced to representations of finite groups by looking at interaction between the action of the ring of endomorphisms and the Galois action on points of small order in that abelian variety.

Oct 8
3:10-4
RH 308		 Siguna Mueller
On the Tonelli - Shanks Algorithm and Applications to Primality Testing
 

Abstract: There seem to be different descriptions of the Tonelli - Shanks root finding algorithm in the literature. We are investigating their behavior when applied to composite numbers (instead of primes). We also explore a modification that could very efficiently be combined with the Berrizbeitia-Berry 'omega-test'. The results could lead to significant improvements to probabilistic primality tests for numbers n=1mod8. So far, I have only tested the basic ideas and the new algorithm is definitely performing better than some of the very recent sophisticated tests by Browkin. Most of these are very new ideas, and all is work in progress.

Oct 1 Stefan Erickson, Dept. of Mathematics & Computer Science Colorado College
 
Explicit Formulas for Real Hyperelliptic Curves of Genus 2
 

Abstract: The infrastructure of real hyperelliptic curves has been proposed for use in cryptographic protocols. Although the arithmetic of real curves is generally slower than imaginary curves, recent work has shown that some divisor additions can be replaced with faster baby steps. In order to make a fair comparison with protocols using imaginary curves, explicit formuals for divisor addition and doubling on real curves are needed. We present explicit formulas for genus 2 real hyperelliptic curves and compare the results with imaginary curves.

Spring 2007
 
Apr 24 Siguna Mueller Rational Biquadratic Reciprocity
 

Abstract: Quadratic reciprocity enables us to completely characterize primes p for which a given prime q is a square. When generalizing these questions we have to deal with higher reciprocity laws. For instance, in order to characterize the primes p for which a given prime q is a fourth power we require the biquadratic symbol in the ring of the Gaussian integers. On the other hand, as G.H. Hardy observed, 'It is ordinary rational arithmetic which attracts the ordinary man...'. In particular, rational biquadratic reciprocity deals with the case that the quartic symbol only assumes real values. We consider some special cases that have been known since Dirichlet. We are interested in some possible generalizations and pose some open questions. This is work in progress.
Feb 6 Bryan Shader Fastest Mixing Markov Chains
 

Abstract: An increasingly important computational tool in combinatorics is the Markov Chain-Monte Carlo method for sampling a large set of combinatorial objects. We discuss an interesting problem, first introduced by P. Diaconis, related to the MCMC method. In short, given the structure of a Markov Chain (i.e. the ways in that states can change) how should the transition probabilities be assigned so that the Markov Chain converges to its steady-state most quickly?
Jan 30 Chanyoung Shader Multiplicities of Irreducible Representations of General Linear Lie superalgebras
 

Abstract: In this talk, I will introduce the general linear Lie superalgebras and their finite dimensional irreducible representations. In particular, I will discuss the weight space decomposition of such irreducible representations, and asymptotic behavior of the weights as the rank of the algebra gets larger.

This talk will focus on general problems, results and methods which are common in a representation (Lie) theory, ( in the context of the general Linear Lie superalgebras), and will not assume previous knowledge on Lie theory.
Jan 23 Eric Moorhouse The Back-and-Forth Technique
 

Abstract: The Cantor-Bernstein-Schroeder Theorem says that if A and B are sets and there exist injections A->B and B->A, then there exists a bijection A->B. One proof of this result will be described, illustrating the "back-and-forth" technique (so named by Model Theorists). Other instances of this technique will be given, arising in infinite graph theory (the "random graph") and incidence geometry (the "highly transitive projective plane").
Most of this talk will be accessible to a general student audience; the necessary set-theoretic background will be summarized during the talk.

Fall 2006
Dec 4 Bryan Shader Q vs R and R vs C
 

Abstract:Let F be a field and let A by an m by n (0,1)-matrix. The set all all m y n matrices over F with zero-nonzero pattern A is denoted by F(A), and the minimal rank of a matrix in F(A) is denoted by mr(F(A)). In this talk we present matrices A and B such that mr(R(A))< mr(Q(A) and mr R(A) < mr C(A).
Nov 14 Eric Moorhouse Characterizing polynomials of degree at most 2
 

Abstract: Every function f:F->F (F a finite field) is representable as a polynomial (e.g. by interpolation). The function f gives rise to a complex number S_f called the exponential sum of f. We present a result characterizing polynomials of small degree by their exponential sum.
Nov 7 Chanyoung Lee Shader Characters of Representations of Lie Superalgebras of type C
 

Abstract:Character formulas for the finite dimensional irreducible representations of the classical Lie superalgebras are not known in general.
For Lie superalgebras of type C, the representations are classified into two classes, typical and atypical.  A character formula for typical class was given by V. Kac, and this was extended to atypical class by J. Van der Jeught. These character formulas are similar to those given by H. Weyl in the classical Lie algebra context.
In this talk, I will present an alternative formulation of the characters for all finite dimensional irreducible representations of Lie superalgebras of type C using tableaux which unifies the formulas by Kac and Van der Jeught.
Oct 31 Pedro Berrizbeitia A Generation of Miller's Primality Theorem
    ***Will be held in RH 342***

***@ 2:10 pm***
 

Abstract:This is joint work with Aurora Olivieri, at University Simon Bolivar.
In the 1970's, Miller showed that under the assumption of ERH (Extended Riemann Hypothesis), the smallest witness for the strong pseudoprime test is $O(\log n)^2$. This leads to an ERH Conditional Primality Test that runs in time $\~O(\log n)^4$. Let $r \ge 2$ be a positive integer. Let $A_r$ be the set of integers whose divisors are congruent to $1$ modulo $r$. In the 1990's, Berry and I introduced, for numbers $n$ in $A_r$, the concept of $\omega$-prime to base $a$, which generalizes the concept of strong pseudoprime. For such numbers we produced a probabilistic test with probability of failure less than $frac{1}{2r}$, generalizing the Rabin-Monier Theorem. Here we show that under ERH the smallest witness for these $r$-test is also $O(\log n)^2$, hence we produce, for each $r$, an ERH Conditional Primality Test that runs in $\~O(\log n)^4$, for number $n \equiv 1 \pmod r$. All concepts will be explained in the talk. Issues on the complexity and comparison with other test will also be discussed.
Oct 24 Derrick Cerwinsky Sieves of Thunder: The race for the Pseudosquares
 

Abstract: While a polynomial time algorithm exists for primality proving, it is dependent on knowing the value of pseudosquares.
In this talk we will look at the challenges faced in seeking the pseudosquares, as well as sieving techniques spanning from the times of the ancient Greeks to the state of the art; and one student's quest to understand them all.
This talk assumes no background in number theory or algebra so graduate students are strongly encouraged to attend.
Oct 17 Andreas Stein Approximating Euler Products and an Algorithm for Computing the Class Number of an Algebraic Function Field
 

Abstract: A fundamental problem in the theory of function fields and curves over finite fields is the effective computation of the class number h and thus the order of the Jacobian of an algebraic function field. If the characteristic of the finite field is small, various recent algorithms solve this problem. Our main focus will be algebraic function fields of large characteristic, in which case not much is known about effective computation of the order of the Jacobian. However, our methods are very general for any genus and any characteristic. In our talk, we will first discuss how to perform arithmetic in an algebraic

function fields based on recent results. Then we will provide tight estimates for the class number via truncated Euler products, and show how these estimates can be used to develop an effective method of computing.
Oct 3 Bryan Shader Chasing after a resolution of the 2n conjecture
 

Abstract: The sign pattern
[+ - 0 0 0]
[+ 0 - 0 0]
[+ 0 0 - 0]
[+ 0 0 0 -]
[+ 0 0 0 -]
is spectrally arbitrary in the sense that every monic real polynomial of degree 5 is the characteristic polynomial of at least one real matrix with this sign pattern.
The 2n-conjecture asserts that an n by n spectrally arbitrary, sign pattern has at least 2n nonzero entries. In this talk we discuss various attacks on the 2n conjecture.
The 2n-conjecture is the focus of an upcoming workshop at the American Institute of Mathematics in Palo Alto.
Sept 26 Sylvia Hobart Removing an eigenvalue from a graph
 

Abstract: Let G be a graph with vertex set V, and r an eigenvalue of G of multiplicity m.

A star set for r is a set X of m vertices of G such that the induced subgraph on V-X does not have r as an eigenvalue.

I will show that star sets always exist, and some consequences of this.

(The talk is based on work of Dragos Cvetkovic, Peter Rowlinson, and Slobodan Simic.
It should be accessible to graduate students.)
Sept 19 Siguna Mueller Cubic Reciprocity and Cubic Residuacity

Abstract: Much work has been done on quadratic residuacity. Given a prime q, there are simple criteria for determining all primes p such that the quadratic character (q/p) has a preassigned value 1 or -1.

The theory for cubic residuacity is known to be more involved. For a given prime q the classification of all primes p with a certain cubic character (q/pi)_3 is tied to the splitting of the prime p into its divisor(s) pi in the ring of the Eisenstein integers. We extend on previous work of E. Lehmer, K.S. Williams and Zhi-Hong Sun. Our contribution is a simpler and unified theory. It seems that our setting is the natural environment to handle cubic residuacity. As a consequence, we show that being able to distinguish between the three character values is equivalent to the Cubic Reciprocity Law.

Joint work with Boris Iskra and Pedro Berrizbeitia (both, University of Simon Bolivar, Caracas, Venezuela).
Sept 12 Eric Moorhouse Embedding Partial Linear Spaces in Finite Projective Planes

Abstract: A partial linear space is a point-line incidence structure in which no two points are on more than one line. A projective plane is a point-line incidence structure in which every pair of points lie on exactly one line, and every pair of lines meet in exactly one point. (The fine print includes an additional requirement in each case for nondegeneracy, but this does not concern us.)

A natural question is whether every finite partial linear space can be extended to a finite projective plane. I will report on recent joint work with Jason Williford which is motivated by this question.
Sept 5 Andreas Stein New Results on Real Hyperelliptic Curve Arithmetic

Abstract: The generic model for arithmetic on hyperelliptic curve arithmetic is called the imaginary model. In this talk, we will discuss the so-called real model of a hyperelliptic curve.

The details of the arithmetic is technically more involved, but turned out to be more flexible because of an additional much faster operation.  Our main application of these ideas will be in cryptographic protocols based on hyperelliptic curve arithmetic. Using generic divisor arithmetic, the real model analogue of the Diffie-Hellman key exchange protocol is almost fifteen percent faster than conventional key exchange using imaginary hyperelliptic curves, with the most significant improvements occurring for low genus. This speed-up is established theoretically and confirmed numerically.

The ideas of the improvements can be easily generalized to other cryptographic protocols where a similar speed-up can be obtained.  These results exclude explicit formulas for low genus curves.Explicit formulas for genus two and three real hyperelliptic curves are currently developed and optimized. We remark that the same ideas lead to equivalent speed-ups in protocols based on the arithmetic in real quadratic number field arithmetic.