The ADM Seminar typically meets on Thursdays, 3:30-4:30, in Martin M-102.
* Refreshments at 3:00 in Martin O 1st floor foyer
** denotes special time
TITLE:
Labelings and direction trees in near-critical convex configurations
SPEAKER:
Robert E. Jamison
AFFILIATION: Clemson University
ABSTRACT:
A direction tree on a finite set of points X in the real plane is a
tree whose vertices are the points of X and whose edges all have
different slopes, where the slope of an edge is the slope of the line passing
through its endpoints. It is a consequence (cf. Discrete Comput Geom 2
(1987), 249-254) of a celebrated result of Peter Ungar (JCTA 33 (1982),
343-347) that any finite set of noncollinear (i.e., not all on a line)
points determine a direction tree.
There are several obvious criteria which limit the possible structure of direction trees. The goal here is to find nonobvious structural limitations when X determines few slopes and lies essentially on the boundary of a convex polygon.
One special family of such configurations consists of the bicolumnar
arrays BC(s,t), which consist of s+1 evenly spaced points on a vertical
line and t+1 evenly spaced points on a parallel line. It turns out that
the realization of a tree as a direction tree of BC(s,t) avoiding
the infinite slope corresponds to a vertex labeling which is similar in
some ways to the well-known notion of graceful labeling. Here negative
labels are also allowed but must alternate with positive labels. Sums,
rather than absolute values of differences, are the induced edge labels
and must be distinct. In contrast to the known results in
the graceful case, it turns out that some trees do not have bigraceful
labelings.
Similarly the question of when a tree is a direction tree of a regular
polygon also reduces to a labeling question whose solution results in some
interesting number theoretic conditions
.
TITLE:
Codes, designs, and groups
SPEAKER:
J. D. Key
AFFILIATION: Clemson University
ABSTRACT:
Many of the important properties of codes that come from designs, particularly
those from finite-geometry designs, can be deduced from the geometrical
properties of the designs. For example, the dimension of the code, the
minimum weight, and sometimes the weight-enumerator, can be found in this
way. Also decoding algorithms that essentially use the geometric properties
of the design can be of use: in particular, the use of majority-logic decoding
for the dual codes of those from projective planes was one of the original
stimuli that brought design and coding theory together.
In a similar way the automorphism group of the design will also act on the code, and if the design has a lot of symmetry and the group is large, decoding algorithms using the group can be of use. Permutation decoding requires the knowledge of a basis for the code, and an ordering of the coordinate positions to give the information symbols. Earlier work on codes of projective planes has found bases, in particular bases of minimum-weight vectors. This has led to a convenient way to find a suitable set of information positions in the case of desarguesian projective planes.
In this talk I will show how these bases of minimum-weight vectors can be used for permutation decoding, and illustrate an infinite class of cases where a partial decoding can be established.
TITLE:
Recursive matrices and counting configurations of kings
SPEAKER:
Neil Calkin
AFFILIATION: Clemson University
ABSTRACT:
We will discuss various enumeration questions arising in statistical
mechanics (focusing on the problem of counting the number of configurations
of non-attacking kings on a chessboard) and show how these types of questions
give rise to problems involving estimating eigenvalues of recursively defined
matrices. We will discuss various ways of obtaining estimates and
bounds for the eigenvalues.
TITLE:
Bounds for the minimum weight of the dual codes of some classes of designs
SPEAKER:
Kelle Clark
AFFILIATION: Queens University
ABSTRACT:
A design D=(P, B, I) consists of a set of points P, a set of blocks
B and an incidence relation I between the points and the blocks.
For example, one can simply think of a block as being a subset of points
and the incidence relation as point-set containment. The study of
designs had its origin in statistics and has links with many areas of mathematics
including group theory, geometry and coding theory. In particular,
a linear code can be generated from a design (P,B,I) by taking the subspace
of Fp|P| spanned by the incidence vectors of the
blocks in B.
A code's usefulness in applications is dependent on the code's parameters, in particular a linear code's error-detection/error-correction capabilities are determined by its minimum weight. The relationship between the linear code of a design and the design can be exploited to determine bounds for the parameters of the code as well as to identify substructures in the design. The results given by these relations are often presented without any mention of the methods used in the proofs. This talk will focus on recent results submitted by J. D. Key, H. N. Ward and the speaker that address the minimum weight of the dual codes of projective planes of order 25 along with some discussion of the most interesting details of their proofs. The talk will be accessible to a general audience.
TITLE:
Divisibility properties of partition functions
SPEAKER:
Dave Penniston
AFFILIATION: Furman University
ABSTRACT:
Ever since S. Ramanujan proved his famous congruences for the unrestricted
partition function modulo 5, 7 and 11, there has been considerable interest
in the question of divisibility of partition functions, both unrestricted
and restricted. In this talk we discuss the class of p-regular partition
functions, which exhibits some very interesting arithmetic behavior, and
present some divisibility results for them.
TITLE:
Subspace subcodes of Reed-Solomon codes
SPEAKER: Sarah Spence
AFFILIATION: Olin College of Engineering
ABSTRACT:
Subspace subcodes of Reed-Solomon (SSRS) codes, formed by taking certain
subsets of Reed-Solomon codes, were introduced by Hattori, McEliece, Solomon,
and Lin in the mid-1990's. These authors found a complicated dimension
formula and a simple lower bound on the dimension for SSRS codes over
GF(2m). In this talk, we will present a proof of a conjecture
of Hattori concerning how to identify subspaces that give an SSRS code
whose dimension exceeds the lower bound. We will also mention some
connections to Goppa, Srivastava, and Chein-Choy generalized BCH codes.
TITLE:
Polynomials with restricted coefficients and prescribed noncyclotomic factors
SPEAKER: Michael Mossinghoff
AFFILIATION: Davidson College
ABSTRACT:
Let N denote the set of polynomials whose coefficients are all 0 or
1with constant term 1. It is easy to construct polynomials in N having
repeated cyclotomic factors. For example, the polynomial (x+1)
(x3+1)(x7+1)...(x2m-1+1) has (x+1)m
as
a factor. In 1993, Odlyzko and Poonen asked if there exist polynomials
in this set with repeated noncyclotomic factors. We describe some
algorithms for searching for polynomials in N with prescribed noncyclotomic
factors, and provide an answer to this question using polynomials that
are in a sense very nearly cyclotomic. We also consider similar problems
regarding polynomials with coefficients lying in the fixed sets {-1,1}
or {-1,0,1} and their connections with a conjecture of Lehmer regarding
polynomials with small Mahler measure.
TITLE:
Recent progress on the primitive polynomials existence problem
SPEAKER:
Donald Mills
AFFILIATION: Southern Illinois
University
ABSTRACT:
Let Fq denote the finite field of q elements, q a
prime power, and let Fq^n denote the extension field of degree
n over Fq. A primitive element a in Fq^n is
a nonzero element serving as a generator of the cyclic group Fq^n*=Fq^n
\
{0} under ordinary multiplication. The (monic) polynomial f(x) in Fq[x]
of degree n with root a is a primitive polynomial of degree
n over Fq. Such polynomials find use in various coding-theoretic
and cryptographic applications.
Now set f(x)=xn+sumi=1nfixn-i. In the past fifteen years, questions of the following general form have been raised: Given a finite field Fq, a positive integer n, elements a1, a2,...,ak in Fq, k < \frac{n}{2}+1, and distinct integers 0< i1, i2,..., ik <n+1 does there exist a primitive polynomial f(x) in Fq[x] of the above-prescribed form, with fi_j=aj for j=1, 2,..., k? The case where k=i1=1 was resolved by Jungnickel and Vanstone, and independently by Cohen, around 1990. The case where q is odd, n>6, k=2, i1=1 and i2=2 was addressed by Han in a 1996 paper. Recently, Cohen and the speaker have refined Han's arguments as well as resolved the cases n=5 and n=6. Even more recently, the speaker has resolved the case where the characteristic of the finite field is at least five, n>8, k=3, and ij=j for j from 1 to 3. Almost simultaneously, Han and Fan addressed the same problem using Galois rings. While their results for smaller n were not as strong as the speaker's, their approach is independent of the characteristic of the underlying field. The main thrust of the talk will be the speaker's approaches to the cases k=2 and k=3, with a secondary emphasis on the work of Fan and Han. The talk will conclude with a discussion of prospects to combine the best aspects of the two methods so as to yield a strong result that is characteristic-independent for general values of k.
TITLE:
Unusual properties of PG(2,q)
SPEAKER:
Arthur Sherk
AFFILIATION: University of Toronto
ABSTRACT:
The Desarguesian finite projective plane of order q (a prime power)
can be exhibited in terms of a perfect difference set D of order q. This
amounts to defining PG(2,q) in terms of a cubic extension K of the field
GF(q).
Using some obvious properties of D and K, we find that they induce unexpected results in PG(2,q).
TITLE:
Application of iterative-decoding techniques to communication systems using
algebraic codes
SPEAKER: Dan
Noneaker
AFFILIATION: Holcombe Department of Electrical and Computer Engineering,
Clemson University
ABSTRACT:
One of the most important developments in communication theory in the
past decade has been the introduction of a class of iterative-decoding
techniques and corresponding code-design methods that yield very good communication-system
performance for a wide range of communication channels. The iterative-decoding
algorithms employ real-valued or complex-valued ("soft") inputs and outputs
that are exchanged among multiple decoding stages using feedback that is
somewhat analogous to the design of a turbo charger in an automobile engine.
Hence, the decoding techniques are sometimes referred to as "turbo decoding,"
and the corresponding codes are sometimes referred to as "turbo codes."
It has been shown that the Shannon capacity of an additive, white Gaussian
noise channel can be approached at error probabilities of practical interest
using properly-designed turbo codes and iterative decoding of reasonable
algorithmic complexity, and good performance is also possible in a variety
of other channels.
Most of the research on soft-input, soft-output (SISO) iterative decoding has focused on its use with codes that are constructed from "constituent codes" that are most naturally described in terms of a trellis structure (such as convolutional codes) or a graph structure (such as low-density parity-check codes). In this presentation, we will examine the use of SISO iterative decoding in a system that employs one algebraic constituent code. In particular, we will focus on its application to a slow-frequency-hop spread-spectrum communication system that employs a Reed-Solomon outer code together with a differential modulation format used as a simple, recursive inner encoder. A method for SISO iterative decoding is described that uses algebraic decoding of the outer code as one of the constituent decoders. Both single-pass errors-and-erasures decoding and generalized-minimum-distance decoding for the algebraic constituent decoder are addressed.
TITLE:
Primality testing
SPEAKER: Richard P.
Brent
AFFILIATION: Oxford University
ABSTRACT:
We consider the classical problem of testing if a given (large) number
is prime or composite. First we outline some of the efficient randomized
algorithms for solving this problem.
For many years it has been an open question whether a deterministic
polynomial time algorithm exists for primality testing, i.e. whether "PRIMES
is in P". Recently Agrawal, Kayal and Saxena answered this question
in the affirmative. They gave a surprisingly simple deterministic
algorithm. We describe their algorithm, mention some improvements by Bernstein
and Lenstra, and consider whether the algorithm is useful in practice.
TITLE:
Some excursions in network modeling
SPEAKER: Doug
Shier
AFFILIATION: Clemson University
ABSTRACT:
Our modern technological world provides ample evidence of networks,
such as computer networks, transportation networks, and power distribution
networks. What are more intriguing are those conceptual (rather than physical)
networks that are lurking just beneath the surface of seemingly innocent
problems.
In this expository talk, we will first review some fundamental concepts related to shortest paths (and its associated dual problem). These ideas will be applied to some interesting problems that arise in apparently unrelated domains: specifically, artificial intelligence (temporal reasoning) and decision analysis (ranking procedures).
TITLE:
List multi-colorings and Hall's condition
SPEAKER: Evan
B. Wantland
AFFILIATION: Warren Wilson College
ABSTRACT:
Let C be an infinite set of colors, F the collection of finite subsets
of C, G a simple graph, L :V(G)->F a list assignment, and k:V(G)->{0,1,2,3,...}
a color demand function. A proper (L,k)-coloring of G is a function f:V(G)->F
satisfying for all u, v in V(G): (i) f(v) < L(v) , (ii)
#f(v) = #k(v), and (iii) if u and v are adjacent, then f(u) and f(v) are
disjoint. The great game in the study of these list multi-colorings is
to discover circumstances-conditions on G, L and k under which a proper
(L,k)-coloring of G is guaranteed to exist. In this presentation we will
present a few of the results obtained thus far as well as a little motivation
and history. Believe it or not, one could (however loosely) trace
this all the way back to Philip Hall's famous result on Systems of Distinct
Representatives...and in fact we will do just this presenting a similar
generalized condition for Systems of G-Distinct Multi-representatives.
TITLE:
Carmichael numbers with many prime factors
SPEAKER: Jon Grantham
AFFILIATION: Institute for Defense Analyses/Center for Computing
Sciences
ABSTRACT:
This talk represents joint work with W. R. Alford. We give an
algorithm that allows construction of Carmichael numbers with a large number
of prime factors. A carmichael number constructed by our algorithm
has the property that many of its divisors are also Carmichael numbers.
We use this property to perform a computation showing the existence of
Carmichael numbers with k prime factors, for all k from 3 to n. n
is a very large number whose final value will be determined by computations
performed between the writing of this sentence and the giving of this talk.
Algebra & Discrete Mathematics Seminar Fall 2002
Algebra & Discrete Mathematics Seminar Fall 1999-Spring 2002