skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Attention:

The DOI auto-population feature in the Public Access Repository (PAR) will be unavailable from 4:00 PM ET on Tuesday, July 8 until 4:00 PM ET on Wednesday, July 9 due to scheduled maintenance. We apologize for the inconvenience caused.


Title: Upper Tail Large Deviations for Arithmetic Progressions in a Random Set
Abstract Let Xk denote the number of k-term arithmetic progressions in a random subset of $$\mathbb{Z}/N\mathbb{Z}$$ or $$\{1, \dots , N\}$$ where every element is included independently with probability p. We determine the asymptotics of $$\log \mathbb{P}\big (X_{k} \ge \big (1+\delta \big ) \mathbb{E} X_{k}\big )$$ (also known as the large deviation rate) where p → 0 with $$p \ge N^{-c_{k}}$$ for some constant ck > 0, which answers a question of Chatterjee and Dembo. The proofs rely on the recent nonlinear large deviation principle of Eldan, which improved on earlier results of Chatterjee and Dembo. Our results complement those of Warnke, who used completely different methods to estimate, for the full range of p, the large deviation rate up to a constant factor.  more » « less
Award ID(s):
1362326
PAR ID:
10249538
Author(s) / Creator(s):
; ; ;
Date Published:
Journal Name:
International Mathematics Research Notices
Volume:
2020
Issue:
1
ISSN:
1073-7928
Page Range / eLocation ID:
167 to 213
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. null (Ed.)
    Abstract The elliptic algebras in the title are connected graded $$\mathbb {C}$$ -algebras, denoted $$Q_{n,k}(E,\tau )$$ , depending on a pair of relatively prime integers $$n>k\ge 1$$ , an elliptic curve E and a point $$\tau \in E$$ . This paper examines a canonical homomorphism from $$Q_{n,k}(E,\tau )$$ to the twisted homogeneous coordinate ring $$B(X_{n/k},\sigma ',\mathcal {L}^{\prime }_{n/k})$$ on the characteristic variety $$X_{n/k}$$ for $$Q_{n,k}(E,\tau )$$ . When $$X_{n/k}$$ is isomorphic to $E^g$ or the symmetric power $S^gE$ , we show that the homomorphism $$Q_{n,k}(E,\tau ) \to B(X_{n/k},\sigma ',\mathcal {L}^{\prime }_{n/k})$$ is surjective, the relations for $$B(X_{n/k},\sigma ',\mathcal {L}^{\prime }_{n/k})$$ are generated in degrees $$\le 3$$ and the noncommutative scheme $$\mathrm {Proj}_{nc}(Q_{n,k}(E,\tau ))$$ has a closed subvariety that is isomorphic to $E^g$ or $S^gE$ , respectively. When $$X_{n/k}=E^g$$ and $$\tau =0$$ , the results about $$B(X_{n/k},\sigma ',\mathcal {L}^{\prime }_{n/k})$$ show that the morphism $$\Phi _{|\mathcal {L}_{n/k}|}:E^g \to \mathbb {P}^{n-1}$$ embeds $E^g$ as a projectively normal subvariety that is a scheme-theoretic intersection of quadric and cubic hypersurfaces. 
    more » « less
  2. Using Auroux’s description of Fukaya categories of symmetric products of punctured surfaces, we compute the partially wrapped Fukaya category of the complement of $k+1$ generic hyperplanes in $$\mathbb{CP}^{n}$$ , for $$k\geqslant n$$ , with respect to certain stops in terms of the endomorphism algebra of a generating set of objects. The stops are chosen so that the resulting algebra is formal. In the case of the complement of $n+2$ generic hyperplanes in $$\mathbb{C}P^{n}$$ ( $$n$$ -dimensional pair of pants), we show that our partial wrapped Fukaya category is equivalent to a certain categorical resolution of the derived category of the singular affine variety $$x_{1}x_{2}\ldots x_{n+1}=0$$ . By localizing, we deduce that the (fully) wrapped Fukaya category of the $$n$$ -dimensional pair of pants is equivalent to the derived category of $$x_{1}x_{2}\ldots x_{n+1}=0$$ . We also prove similar equivalences for finite abelian covers of the $$n$$ -dimensional pair of pants. 
    more » « less
  3. We examine correlations of the Möbius function over $$\mathbb{F}_{q}[t]$$ with linear or quadratic phases, that is, averages of the form 1 $$\begin{eqnarray}\frac{1}{q^{n}}\mathop{\sum }_{\deg f0$$ if $$Q$$ is linear and $$O(q^{-n^{c}})$$ for some absolute constant $c>0$ if $$Q$$ is quadratic. The latter bound may be reduced to $$O(q^{-c^{\prime }n})$$ for some $$c^{\prime }>0$$ when $Q(f)$ is a linear form in the coefficients of $$f^{2}$$ , that is, a Hankel quadratic form, whereas, for general quadratic forms, it relies on a bilinear version of the additive-combinatorial Bogolyubov theorem. 
    more » « less
  4. Abstract Given a sequence $$\{Z_d\}_{d\in \mathbb{N}}$$ of smooth and compact hypersurfaces in $${\mathbb{R}}^{n-1}$$, we prove that (up to extracting subsequences) there exists a regular definable hypersurface $$\Gamma \subset {\mathbb{R}}\textrm{P}^n$$ such that each manifold $$Z_d$$ is diffeomorphic to a component of the zero set on $$\Gamma$$ of some polynomial of degree $$d$$. (This is in sharp contrast with the case when $$\Gamma$$ is semialgebraic, where for example the homological complexity of the zero set of a polynomial $$p$$ on $$\Gamma$$ is bounded by a polynomial in $$\deg (p)$$.) More precisely, given the above sequence of hypersurfaces, we construct a regular, compact, semianalytic hypersurface $$\Gamma \subset {\mathbb{R}}\textrm{P}^{n}$$ containing a subset $$D$$ homeomorphic to a disk, and a family of polynomials $$\{p_m\}_{m\in \mathbb{N}}$$ of degree $$\deg (p_m)=d_m$$ such that $$(D, Z(p_m)\cap D)\sim ({\mathbb{R}}^{n-1}, Z_{d_m}),$$ i.e. the zero set of $$p_m$$ in $$D$$ is isotopic to $$Z_{d_m}$$ in $${\mathbb{R}}^{n-1}$$. This says that, up to extracting subsequences, the intersection of $$\Gamma$$ with a hypersurface of degree $$d$$ can be as complicated as we want. We call these ‘pathological examples’. In particular, we show that for every $$0 \leq k \leq n-2$$ and every sequence of natural numbers $$a=\{a_d\}_{d\in \mathbb{N}}$$ there is a regular, compact semianalytic hypersurface $$\Gamma \subset {\mathbb{R}}\textrm{P}^n$$, a subsequence $$\{a_{d_m}\}_{m\in \mathbb{N}}$$ and homogeneous polynomials $$\{p_{m}\}_{m\in \mathbb{N}}$$ of degree $$\deg (p_m)=d_m$$ such that (0.1)$$\begin{equation}b_k(\Gamma\cap Z(p_m))\geq a_{d_m}.\end{equation}$$ (Here $$b_k$$ denotes the $$k$$th Betti number.) This generalizes a result of Gwoździewicz et al. [13]. On the other hand, for a given definable $$\Gamma$$ we show that the Fubini–Study measure, in the Gaussian probability space of polynomials of degree $$d$$, of the set $$\Sigma _{d_m,a, \Gamma }$$ of polynomials verifying (0.1) is positive, but there exists a constant $$c_\Gamma$$ such that $$\begin{equation*}0<{\mathbb{P}}(\Sigma_{d_m, a, \Gamma})\leq \frac{c_{\Gamma} d_m^{\frac{n-1}{2}}}{a_{d_m}}.\end{equation*}$$ This shows that the set of ‘pathological examples’ has ‘small’ measure (the faster $$a$$ grows, the smaller the measure and pathologies are therefore rare). In fact we show that given $$\Gamma$$, for most polynomials a Bézout-type bound holds for the intersection $$\Gamma \cap Z(p)$$: for every $$0\leq k\leq n-2$$ and $t>0$: $$\begin{equation*}{\mathbb{P}}\left(\{b_k(\Gamma\cap Z(p))\geq t d^{n-1} \}\right)\leq \frac{c_\Gamma}{td^{\frac{n-1}{2}}}.\end{equation*}$$ 
    more » « less
  5. The third Painlevé equation in its generic form, often referred to as Painlevé-III($$D_6$$), is given by $$ \frac{{\rm d}^2u}{{\rm d}x^2} =\frac{1}{u}\left(\frac{{\rm d}u}{{\rm d}x} \right)^2-\frac{1}{x} \frac{{\rm d}u}{{\rm d}x} + \frac{\alpha u^2 + \beta}{x}+4u^3-\frac{4}{u}, \qquad \alpha,\beta \in \mathbb C. $$ Starting from a generic initial solution $$u_0(x)$$ corresponding to parameters $$\alpha$$, $$\beta$$, denoted as the triple $$(u_0(x),\alpha,\beta)$$, we apply an explicit Bäcklund transformation to generate a family of solutions $$(u_n(x),\alpha + 4n,\beta + 4n)$$ indexed by $$n \in \mathbb N$$. We study the large $$n$$ behavior of the solutions $$(u_n(x), \alpha + 4n, \beta + 4n)$$ under the scaling $x = z/n$ in two different ways: (a) analyzing the convergence properties of series solutions to the equation, and (b) using a Riemann-Hilbert representation of the solution $$u_n(z/n)$$. Our main result is a proof that the limit of solutions $$u_n(z/n)$$ exists and is given by a solution of the degenerate Painlevé-III equation, known as Painlevé-III($$D_8$$), $$ \frac{{\rm d}^2U}{{\rm d}z^2} =\frac{1}{U}\left(\frac{{\rm d}U}{{\rm d}z}\right)^2-\frac{1}{z} \frac{{\rm d}U}{{\rm d}z} + \frac{4U^2 + 4}{z}.$$ A notable application of our result is to rational solutions of Painlevé-III($$D_6$$), which are constructed using the seed solution $(1,4m,-4m)$ where $$m \in \mathbb C \setminus \big(\mathbb Z + \frac{1}{2}\big)$$ and can be written as a particular ratio of Umemura polynomials. We identify the limiting solution in terms of both its initial condition at $z = 0$ when it is well defined, and by its monodromy data in the general case. Furthermore, as a consequence of our analysis, we deduce the asymptotic behavior of generic solutions of Painlevé-III, both $$D_6$$ and $$D_8$$ at $z = 0$. We also deduce the large $$n$$ behavior of the Umemura polynomials in a neighborhood of $z = 0$. 
    more » « less