• ### Detection of Planted Solutions for Flat Satisfiability Problems(1502.06144)

March 6, 2019 math.ST, stat.TH, cs.CC, cs.LG
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.
• ### Rational points on solvable curves over $\mathbb{Q}$ via non-abelian Chabauty(1706.00525)

April 3, 2018 math.AG, math.NT
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 non-abelian Chabauty method applies to such a curve. By combining this with results of Bogomolov-Tschinkel 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}$.
• ### Sumsets as unions of sumsets of subsets(1612.01929)

Sept. 7, 2017 math.CO, math.NT
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 Croot-Lev-Pach and Ellenberg-Gijswijt on the cap set problem, together with a result of Meshulam on linear spaces of low-rank matrices. The result is a modest generalization of the recent bounds on (single-colored and multi-colored) sum-free sets by the author and others.
• ### Fox-Neuwirth-Fuks cells, quantum shuffle algebras, and Malle's conjecture for function fields(1701.04541)

Jan. 17, 2017 math.AT, math.AG, math.QA, math.NT
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 Ellenberg-Venkatesh-Westerland, 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.
• ### New bounds on curve tangencies and orthogonalities(1509.05821)

Nov. 3, 2016 math.CO, cs.CG
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})$ curve-curve 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 curve-curve 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 two-rich points in space curve arrangements.
• ### Homology of FI-modules(1506.01022)

Sept. 5, 2016 math.AT, math.CO, math.GT, math.RT
We prove an explicit and sharp upper bound for the Castelnuovo-Mumford regularity of an FI-module 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.
• ### On large subsets of $F_q^n$ with no three-term arithmetic progression(1605.09223)

May 30, 2016 math.CO, math.NT
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})$.
• ### Homological stability for Hurwitz spaces and the Cohen-Lenstra conjecture over function fields(0912.0325)

Dec. 1, 2015 math.AT, math.NT
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 l-group. 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 l-part of their class group isomorphic to A.
• ### Algebraic structures on cohomology of configuration spaces of manifolds with flows(1508.02430)

April 14, 2019 math.AT, math.CO, math.RT
Let PConf^n M be the configuration space of ordered n-tuples of distinct points on a smooth manifold M admitting a nowhere-vanishing vector field. We show that the ith cohomology group with coefficients in a field H^i(PConf^n M, k) is an N-module, 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.
• ### Furstenberg sets and Furstenberg schemes over finite fields(1502.03736)

Feb. 12, 2015 math.CO, math.CA, math.AG
We give a lower bound for the size of a subset of $\mathbb F_q^n$ containing a rich k-plane in every direction, a k-plane Furstenberg set. The chief novelty of our method is that we use arguments on non-reduced subschemes and flat families to derive combinatorial facts about incidences between points and k-planes in space.
• ### FI-modules and stability for representations of symmetric groups(1204.4533)

Oct. 30, 2014 math.AT, math.CO, math.GT, math.RT
In this paper we introduce and develop the theory of FI-modules. 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 n-pointed 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 cycle-counting 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 Church-Farb) for a sequence of S_n-representations is converted to a finite generation property for a single FI-module.
• ### FI-modules over Noetherian rings(1210.1854)

March 2, 2014 math.AT, math.CO, math.GT, math.RT
FI-modules 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 FI-module implies representation stability for the corresponding sequence of S_n-representations. In this paper we prove the Noetherian property for FI-modules over arbitrary Noetherian rings: any sub-FI-module of a finitely generated FI-module 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.
• ### Homological stability for Hurwitz spaces and the Cohen-Lenstra conjecture over function fields, II(1212.0923)

Nov. 19, 2013 math.AT, math.KT, math.NT
We prove a version of the Cohen--Lenstra 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 puncture-stabilization, 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.
• ### An incidence conjecture of Bourgain over fields of positive characteristic(1311.1479)

Nov. 6, 2013 math.CO, math.AG, math.NT
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.
• ### Representation stability in cohomology and asymptotics for families of varieties over finite fields(1309.6038)

Sept. 24, 2013 math.AT, math.AG, math.GT, math.NT, math.GR
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_n-representation V, one can ask how the multiplicity of V in the cohomology groups H*(X_n;Q) varies with n. We explain how the Grothendieck-Lefschetz 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.
• ### Superstrong approximation for monodromy groups(1210.3757)

March 9, 2013 math.NT
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 infinite-index Zariski-dense 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.
• ### Random pro-p groups, braid groups, and random tame Galois groups(1204.4242)

April 19, 2012 math.NT, math.GR
We introduce a heuristic prediction for the distribution of the isomorphism class of the Galois group of the maximal pro-p extension of Q unramified outside a "random" set of primes. This is guided by reasoning similar to that governing the Cohen-Lenstra conjectures. We conclude by describing theoretical and experimental evidence for our heuristic.
• ### Random Dieudonne modules, random p-divisible groups, and random curves over finite fields(1201.0822)

Jan. 4, 2012 math.NT
We describe a probability distribution on isomorphism classes of principally quasi-polarized p-divisible 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 (p-corank, a-number, etc.) of p-divisible groups drawn from this distribution. It is then natural to ask to what extent the p-divisible 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 genus-g curves over F_p whose Jacobian is ordinary approaches the limit that such a heuristic would predict. This heuristic is analogous to conjectures of Cohen-Lenstra type for fields k of characteristic other than p, in which case the random p-divisible 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.
• ### Arithmetic Veech sublattices of $\SL(2,\Z)$(0909.1851)

Aug. 12, 2011 math.GT, math.GR
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.
• ### Upper bounds for the growth of Mordell-Weil ranks in pro-p towers of Jacobians(1001.4266)

Jan. 24, 2010 math.AG, math.NT
We study the variation of Mordell-Weil ranks in the Jacobians of curves in a pro-p tower over a fixed number field. In particular, we show that under mild conditions the Mordell-Weil 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 Mantilla-Soler on the Mordell-Weil rank of the modular Jacobian J(Np^m).
• ### Linnik's ergodic method and the distribution of integer points on spheres(1001.0897)

Jan. 6, 2010 math.DS, math.NT
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 large-deviation 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).
• ### Positive motivic measures are counting measures(0907.0488)

July 2, 2009 math.AG
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.
• ### A sharp diameter bound for unipotent groups of classical type over Z/pZ(math/0510506)

Oct. 24, 2005 math.CO, math.GR
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)
• ### On the error term in Duke's estimate for the average special value of L-functions(math/0311131)

May 7, 2005 math.NT
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 Q-curves 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 L-functions 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.
• ### Galois representations attached to Q-curves and the generalized Fermat equation A^4 + B^2 = C^p(math/0311497)

Nov. 27, 2003 math.AG, math.NT
We show that the mod p Galois representations attached to a Q-curve 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 non-split modular curves, and an analytic argument showing that Jacobians of certain twisted modular curves admit quotients with Mordell-Weil rank 0. In combination with a previous theorem of the author and Skinner on modularity of Q-curves, 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.