
We study the detection problem of finding planted solutions in random
instances of flat satisfiability problems, a generalization of boolean
satisfiability formulas. We describe the properties of random instances of flat
satisfiability, as well of the optimal rates of detection of the associated
hypothesis testing problem. We also study the performance of an algorithmically
efficient testing procedure. We introduce a modification of our model, the
light planting of solutions, and show that it is as hard as the problem of
learning parity with noise. This hints strongly at the difficulty of detecting
planted flat satisfiability for a wide class of tests.

We study the Selmer varieties of smooth projective curves of genus at least
two defined over $\mathbb{Q}$ which geometrically dominate a curve with CM
Jacobian. We extend a result of Coates and Kim to show that Kim's nonabelian
Chabauty method applies to such a curve. By combining this with results of
BogomolovTschinkel and Poonen on unramified correspondences, we deduce that
any cover of $\mathbf{P}^1$ with solvable Galois group, and in particular any
superelliptic curve over $\mathbb{Q}$, has only finitely many rational points
over $\mathbb{Q}$.

Let $S$ and $T$ be subsets of $\mathbf{F}_q^n$. We show there are subsets
$S'$ of $S$ and $T'$ of $T$ such that $S+T$ is the union of $S+T'$ and $S'+T$,
with $S' + T'$ bounded by $c^n$ with $c < q$. The proof relies on the
method of CrootLevPach and EllenbergGijswijt on the cap set problem,
together with a result of Meshulam on linear spaces of lowrank matrices. The
result is a modest generalization of the recent bounds on (singlecolored and
multicolored) sumfree sets by the author and others.

The purpose of this paper is to prove the upper bound in Malle's conjecture
on the distribution of finite extensions of $\mathbb{F}_q(t)$ with specified
Galois group. As in previous work of EllenbergVenkateshWesterland, our result
is based upon computations of the homology of braid groups with certain
(exponential) coefficients. However, the approach in this paper is new, relying
on a connection between the cohomology of Hurwitz spaces and the cohomology of
quantum shuffle algebras.

We establish new bounds on the number of tangencies and orthogonal
intersections determined by an arrangement of curves. First, given a set of $n$
algebraic plane curves, we show that there are $O(n^{3/2})$ points where two or
more curves are tangent. In particular, if no three curves are mutually tangent
at a common point, then there are $O(n^{3/2})$ curvecurve tangencies. Second,
given a family of algebraic plane curves and a set of $n$ curves from this
family, we show that either there are $O(n^{3/2})$ points where two or more
curves are orthogonal, or the family of curves has certain special properties.
We obtain these bounds by transforming the arrangement of plane curves into
an arrangement of space curves so that tangency (or orthogonality) of the
original plane curves corresponds to intersection of space curves. We then
bound the number of intersections of the corresponding space curves. For the
case of curvecurve tangency, we use a polynomial method technique that is
reminiscent of Guth and Katz's proof of the joints theorem. For the case of
orthogonal curve intersections, we employ a bound of Guth and the third author
to control the number of tworich points in space curve arrangements.

We prove an explicit and sharp upper bound for the CastelnuovoMumford
regularity of an FImodule V in terms of the degrees of its generators and
relations. We use this to refine a result of Putman on the stability of
homology of congruence subgroups, extending his theorem to previously excluded
small characteristics and to integral homology while maintaining explicit
bounds for the stable range.

In this note, we show that the method of Croot, Lev, and Pach can be used to
bound the size of a subset of $F_q^n$ with no three terms in arithmetic
progression by $c^n$ with $c < q$. For $q=3$, the problem of finding the
largest subset with no three terms in arithmetic progression is called the `cap
problem'. Previously the best known upper bound for the cap problem, due to
Bateman and Katz, was $O(3^n / n^{1+\epsilon})$.

We prove a homological stabilization theorem for Hurwitz spaces: moduli
spaces of branched covers of the complex projective line. This has the
following arithmetic consequence: let l>2 be prime and A a finite abelian
lgroup. Then there exists Q = Q(A) such that, for q greater than Q and not
congruent to 1 modulo l, a positive fraction of quadratic extensions of F_q(t)
have the lpart of their class group isomorphic to A.

Let PConf^n M be the configuration space of ordered ntuples of distinct
points on a smooth manifold M admitting a nowherevanishing vector field. We
show that the ith cohomology group with coefficients in a field H^i(PConf^n M,
k) is an Nmodule, where N is the category of noncommutative finite sets
introduced by Pirashvili and Richter. Studying the representation theory of N,
we obtain new polynomiality results for the cohomology groups H^i(PConf^n M,
k). In the case of unordered configuration space Conf^n M = (PConf^n M)/S_n and
rational coefficients, we show that cohomology dimension in fixed degree is
nondecreasing.

We give a lower bound for the size of a subset of $\mathbb F_q^n$ containing
a rich kplane in every direction, a kplane Furstenberg set. The chief novelty
of our method is that we use arguments on nonreduced subschemes and flat
families to derive combinatorial facts about incidences between points and
kplanes in space.

In this paper we introduce and develop the theory of FImodules. We apply
this theory to obtain new theorems about:
 the cohomology of the configuration space of n distinct ordered points on
an arbitrary (connected, oriented) manifold
 the diagonal coinvariant algebra on r sets of n variables
 the cohomology and tautological ring of the moduli space of npointed
curves
 the space of polynomials on rank varieties of n x n matrices
 the subalgebra of the cohomology of the genus n Torelli group generated by
H^1 and more.
The symmetric group S_n acts on each of these vector spaces. In most cases
almost nothing is known about the characters of these representations, or even
their dimensions. We prove that in each fixed degree the character is given,
for n large enough, by a polynomial in the cyclecounting functions that is
independent of n. In particular, the dimension is eventually a polynomial in n.
In this framework, representation stability (in the sense of ChurchFarb) for a
sequence of S_nrepresentations is converted to a finite generation property
for a single FImodule.

FImodules were introduced by the first three authors in [CEF] to encode
sequences of representations of symmetric groups. Over a field of
characteristic 0, finite generation of an FImodule implies representation
stability for the corresponding sequence of S_nrepresentations. In this paper
we prove the Noetherian property for FImodules over arbitrary Noetherian
rings: any subFImodule of a finitely generated FImodule is finitely
generated. This lets us extend many of the results of [CEF] to representations
in positive characteristic, and even to integral coefficients. We focus on
three major applications of the main theorem: on the integral and mod p
cohomology of configuration spaces; on diagonal coinvariant algebras in
positive characteristic; and on an integral version of Putman's central
stability for homology of congruence subgroups.

We prove a version of the CohenLenstra conjecture over function fields
(completing the results of our prior paper). This is deduced from two more
general theorems, one topological, one arithmetic: We compute the direct limit
of homology, over puncturestabilization, of spaces of maps from a punctured
manifold to a fixed target; and we compute the Galois action on the set of
stable components of Hurwitz schemes.

In this note we generalize a recent theorem of Guth and Katz on incidences
between points and lines in $3$space from characteristic $0$ to characteristic
$p$, and we explain how some of the special features of algebraic geometry in
characteristic $p$ manifest themselves in problems of incidence geometry.

We consider two families X_n of varieties on which the symmetric group S_n
acts: the configuration space of n points in C and the space of n linearly
independent lines in C^n. Given an irreducible S_nrepresentation V, one can
ask how the multiplicity of V in the cohomology groups H*(X_n;Q) varies with n.
We explain how the GrothendieckLefschetz Fixed Point Theorem converts a
formula for this multiplicity to a formula for the number of polynomials over
F_q (or maximal tori in GL_n(F_q), respectively) with specified properties
related to V. In particular, we explain how representation stability in
cohomology, in the sense of [CF, arXiv:1008.1368] and [CEF, arXiv:1204.4533],
corresponds to asymptotic stability of various point counts as n goes to
infinity.

This document is an expanded version of a lecture presented at a conference
on "Thin Groups and Superstrong Approximation" held at the Mathematical
Sciences Research Institute in February 2012. Superstrong approximation is a
criterion on a finitely generated group, saying that certain Cayley graphs
associated to finite quotients of the group form an expander family. In recent
years, our knowledge about superstrong approximation for infiniteindex
Zariskidense subgroups of arithmetic lattices ("thin groups") has drastically
improved. We briefly survey the construction of monodromy groups, discuss our
(limited) knowledge about whether such groups are thin, and discuss an
application to arithmetic geometry (see the paper "Expander graphs, gonality,
and variation of Galois representations") deriving from recent advances in
superstrong approximation. We conclude by indulging in some speculations about
more general contexts, asking: what are the interesting questions about
"nonabelian superstrong approximation" and "superstrong approximation for
Galois groups?" We discuss the relation of these notions with the Product
Replacement Algorithm and the Bogomolov property for infinite algebraic
extensions of number fields.

We introduce a heuristic prediction for the distribution of the isomorphism
class of the Galois group of the maximal prop extension of Q unramified
outside a "random" set of primes. This is guided by reasoning similar to that
governing the CohenLenstra conjectures. We conclude by describing theoretical
and experimental evidence for our heuristic.

We describe a probability distribution on isomorphism classes of principally
quasipolarized pdivisible groups over a finite field k of characteristic p
which can reasonably be thought of as "uniform distribution," and we compute
the distribution of various statistics (pcorank, anumber, etc.) of
pdivisible groups drawn from this distribution. It is then natural to ask to
what extent the pdivisible groups attached to a randomly chosen hyperelliptic
curve (resp. curve, resp. abelian variety) over k are uniformly distributed in
this sense. For instance, one can ask whether the proportion of genusg curves
over F_p whose Jacobian is ordinary approaches the limit that such a heuristic
would predict. This heuristic is analogous to conjectures of CohenLenstra type
for fields k of characteristic other than p, in which case the random
pdivisible group is defined by a random matrix recording the action of
Frobenius. Extensive numerical investigation reveals some cases of agreement
with the heuristic and some interesting discrepancies. For example, plane
curves over F_3 appear substantially less likely to be ordinary than
hyperelliptic curves over F_3.

We prove that every algebraic curve X defined over the algebraic closure of
the rationals is birational over the complex numbers to a Teichmuller curve.

We study the variation of MordellWeil ranks in the Jacobians of curves in a
prop tower over a fixed number field. In particular, we show that under mild
conditions the MordellWeil rank of a Jacobian in the tower is bounded above by
a constant multiple of its dimension. In the case of the tower of Fermat
curves, we show that the constant can be taken arbitrarily close to 1. The main
result is used in the forthcoming paper of Guillermo MantillaSoler on the
MordellWeil rank of the modular Jacobian J(Np^m).

We discuss Linnik's work on the distribution of integral solutions to
$x^2+y^2+z^2 =d$, as $d$ goes to infinity. We give an exposition of Linnik's
ergodic method; indeed, by using largedeviation results for random walks on
expander graphs, we establish a refinement of his equidistribution theorem. We
discuss the connection of these ideas with modern developments (ergodic theory
on homogeneous spaces, $L$functions).

Let K be a field. A positive motivic measure on the Grothendieck ring
K_0(Var_K) is a homomorphism from K_0(Var_K) to the real numbers assigning a
nonnegative value to every variety. In this note we show that the only positive
motivic measures are the counting measures: measures on K_0(Var_{F_q}) which
send a variety to its number of rational points over some fixed finite
extension of F_q.

The unipotent subgroup of a finite group of Lie type over a prime field Z/pZ
comes equipped with a natural set of generators; the properties of the Cayley
graph associated to this set of generators have been much studied. In the
present paper, we show that the diameter of this Cayley graph is bounded above
and below by constant multiples of np + n^2 log p, where n is the rank of the
associated Lie group. This generalizes a result of the first author, which
treated the case of SL_n(Z/pZ). (Keywords: diameter, Cayley graph, finite
groups of Lie type. AMS classification: 20G40, 05C25)

Let F be an orthonormal basis of weight 2 cusp forms on Gamma_0(N). We show
that various weighted averages of special values L(f \tensor chi, 1) over f in
F are equal to 4 pi + O(N^{1 + epsilon}). A previous result of Duke gives an
error term of O(N^{1/2} log N).
The bound here is used in the author's paper "Galois representations attached
to Qcurves and the generalized Fermat equation A^4 + B^2 = C^p," (to appear,
Amer. J. Math.) to show that certain spaces of cuspforms arising there contain
forms whose Lfunctions have nonvanishing special value.
Version of May 2005: Nathan Ng found an error in the earlier version which
yielded a bound too strong by a factor of log N; this is the corrected version,
as it will appear in Canad. Math. Bull. The change does not affect the
application to the Amer. J. Math. paper.

We show that the mod p Galois representations attached to a Qcurve E of
degree d over an imaginary quadratic number field K are surjective for all p
larger than some constant M_{K,d}, if E has potentially multiplicative
reduction at any prime not dividing 6. The proof uses Mazur's formal immersion
method, a result of Darmon and Merel on nonsplit modular curves, and an
analytic argument showing that Jacobians of certain twisted modular curves
admit quotients with MordellWeil rank 0. In combination with a previous
theorem of the author and Skinner on modularity of Qcurves, the surjectivity
result allows one to show that the generalized Fermat equation A^4 + B^2 = C^p
has no nontrivial primitive solutions for p >= 211.