We prove quantitative polynomial Szemer\'edi-type theorems involving polynomial progressions with shift parameter restricted to the set of shifted primes $\mathbb{P}-1$. The types of configurations covered are distinct degree progressions and progressions involving integer multiples of a fixed polynomial. For nonlinear configurations of length at least three, these results provide the first quantitative versions of such theorems. In the linear case, our results improve on work by the last two authors. Our density bounds are strongest in the case of distinct degree polynomials, where they give polylogarithmic bounds, of the same shape as recent bounds by Shao and Wang with integer shifts. The proofs combine recent quantitative results for polynomial configurations in the integers with quantitative Gowers uniformity bounds of the primes. For multiples of a fixed polynomial, we adapt a comparison argument of Altman and Sawhney to obtain uniformity over the polynomial families produced by the $W$-trick. For distinct degree progressions, we establish a comparison between prime-weighted and unweighted polynomial counts that is uniform throughout the density increment argument and accounts for a possible Siegel zero.
We develop two transition principles for lower-bounding value sets generated by structured sequences over prime fields. A reciprocal-affine family with $M$ internal transitions and bounded quotient multiplicity has image size $\gg \min{M,p}^{8/15}$. This recovers the factorial-residue bound and yields the same exponent...
We give an explicit hitting set of size $\text{poly}(n,d,r)$ for the class of $n$-variate degree-$d$ polynomials whose partial derivative space is bounded by $r$, over any field $\mathbb{F}$ of characteristic zero. In particular, this yields a polynomial sized hitting set for the class of depth-$3$ powering circuits. T...
We present a new lower bound on the number of lattice points of all totally unimodular polytopes, generalizing previous lower bounds on contingency tables, integer flows, and beyond. Our bound is based on the Gurvits capacity convex optimization problem, and thus our result implies an efficient deterministic algorithm...
For every constant-width CNF, we show that linear degree in polynomial calculus (PC) implies exponential size in resolution over constant-degree polynomials, over the same prime field. Applications include exponential lower bounds for CNFs in $\operatorname{Res}(\operatorname{PC}_r/\mathbb{F}_p)$ and hence in $\operato...
Families of plateaued Boolean functions with pairwise disjoint Walsh supports are useful in secondary constructions of cryptographic Boolean functions. Of particular interest are maximum-cardinality families whose members admit no nonzero linear structures. To the best of our knowledge, the previously known general con...
Chen Wang, Xiao-Yan Zhang, Chun-Ming Tang et al.· 0 citations
We address the question of which common differences can arise in arithmetic progressions contained in fractal sets. For a compact set $C\subset\mathbb R$, we investigate not only whether arithmetic progressions occur in $C$, but the full collection of their common differences. More generally, for a finite pattern $P$,...
Samantha Sandberg-Clark, Krystal Taylor, A. Yavicoli· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
