We will prove a version of this fundamental theorem for symmetric polynomials in any number of variables (not just two variables) and describe some applications to questions about polynomials in one variable. For example, you can determine if a quadratic polynomial ax² + bx + c has a repeated root by checking if b² - 4ac = 0 (think about the quadratic formula). We will use symmetric polynomials to see how this kind of rule generalizes to polynomials of higher degree.
Comments: Free Refreshments -- uconnmathclub@gmail.com --

This talk will consist of a sketch of the proof of a single main result linking geometric ideas from the first-order model theory of infinite structures with complexity-theoretic analyses of problems over classes of finite structures. To remove any suspense, the statement of the theorem is as follows:

Theorem: Let K = fin[T^G], where T is a complete k-variable theory with infinitely many finite models up to isomorphism. I. If T is constructible, then K is rosy. II. T is efficiently constructible if and only if K is super-rosy.

Obviously, a great number of definitions are needed (regardless of the reader's background, most likely) to make sense of these assertions. For the time being, it should be understood as a shadow of the ``main current'' of first-order model theory -- namely, Shelah's Classification theory. I take ``efficiently constructible'' -- meaning that models of T can be efficiently recovered from elementary diagrams of subsets -- to be a reasonable substitute for ``classifiable'' in the classical theory. We then seek a hierarchy of structural properties culminating in efficient constructibility in analogy with the stability-theoretic hierarchy, Stable properly contains Super-stable properly contains Classifiable=Super-stable+NDOP. In the classical scenario, any non-trivial bound on the number of models of the theory in each cardinality imposes stability, which already supports the rudimentary notion of geometry known as non-forking independence. In the scenario of this study, the hypothesis of constructibility by an algorithm cursorily imitating that of an efficient algorithm in form (meaning, an essentially inflationary program which isn't necessarily efficient) is sufficient to impose another rudimentary notion of geometry on the class of models -- in this case, known as thorn-independence in a rosy class; this is the content of I of the Theorem. The further requirement of efficiency -- polynomially-bounded running times -- induces a further guarantee of good behavior in the geometry of thorn-independence, and the "only if" portion of II of the theorem amounts to just this fact. It turns out, then, that this additional tractability in the geometry gives enough purchase to devise an efficient algorithm, initially disguised as a weak model-theoretic coordinatization result, for the class of the theory's finite models.

For a computable field F, the splitting set S_F of F is the set of polynomials with coefficients in F which factor over F, and the root set R_F of F is the set of polynomials with coefficients in F which have a root in F.

Results of Frohlich and Shepherdson from 1956 imply that for a computable field F, the splitting set S_F and the root set R_F are Turing-equivalent. Much more recently, R. G. Miller showed that for algebraic fields, the root set actually has slightly higher complexity: for algebraic fields F, it is always the case that S_F 1-reduces to R_F, but there are algebraic fields F where we have R_F not 1-reducible to S_F.

Here we compare the splitting set and the root set of a computable algebraic field under a different reduction: the bounded Turing reduction. We construct a computable algebraic field for which R_F does not bT-reduce to S_F.

We also define a Rabin embedding g of a field into its algebraic closure, and for a computable algebraic field F, we compare the relative complexities of R_F, S_F, and g(F) under m-reducibility and under bT-reducibility.

We investigate computable equivalence structures, as well as computably enumerable (c.e.) and co-computably enumerable (co-c.e.) equivalence structures. Together with W. Calvert, D. Cenzer, and A. Morozov, we established that a computable equivalence structure A is computably categorical if and only if A has only finitely many finite equivalence classes, or A has only finitely many infinite classes, bounded character, and at most one finite k such that there are infinitely many classes of size k. Moreover, every computably categorical equivalence structure A is relatively computably categorical, that is, A has a c.e. Scott family of existential formulas. We also characterized relatively limit computably categorical equivalence structures as those with finitely many infinite classes or with bounded character. A. Kach and D. Turetsky proved that not all limit computably categorical equivalence structures are relatively limit computably categorical.

Together with D. Cenzer and J. Remmel we further studied c.e. and co-c.e. equivalence structures. While any c.e. equivalence structure with infinitely many infinite classes is isomorphic to a computable structure, there are c.e. equivalence structures that are not isomorphic to computable ones. We showed that if c.e. equivalence structures A and B are isomorphic to a computable structure that is relatively limit computably categorical, then A and B are limit computably isomorphic. On the other hand, for every computable relatively limit computably categorical equivalence structure that is not computably categorical, we construct an isomorphic co-c.e. structure that is not limit computably isomorphic to any computable, even. c.e. structure.