The true quantitative range of primes and polynomial values with restricted digits: minimal base, digit-exclusion density, polynomial-degree dependence, and effective error terms

Maynard's paper 'Primes and Polynomials With Restricted Digits' proved by the Hardy-Littlewood circle method that for every integer base $q>2{,}000{,}000$ and every digit $a_0$ there are infinitely many primes - indeed the expected asymptotic count of primes - whose base-$q$ expansion omits $a_0$, with analogues for values of integer polynomials of degree $r$ (base $q>\exp(\exp(2r))$) and for excluding several digits ($s<q^{1/5-\epsilon}$, or $q-s\ge q^{4/5+\epsilon}$ for consecutive excluded digits). The paper itself records that these ranges are far from optimal: it conjectures the single-digit result holds for every base $q>2$, and anticipates that bilinear (Type I/II) sums, Harman's sieve, zero-density estimates and stronger Weyl-sum bounds would push all the ranges much further. The problem is to determine the true quantitative range: the single-digit theorem for the still-open bases $3\le q\le 9$ and $q=11$ (apart from the trivially obstructed instance of excluding the digit 1 in base 3, where all allowed digits are even), and the conjectured asymptotic formula in base 10, where only the correct order of magnitude is known; the sharp digit-exclusion density thresholds (even two missing decimal digits is open); the base-versus-degree law for polynomial values toward its essentially linear necessary growth; and effective (Siegel-zero-free) error terms. Maynard's own Inventiones 2019 sequel realized part of the anticipated route (base 10; asymptotics for $q\ge 12$; exclusion thresholds $s\le q^{23/80}$ and $q-s\ge q^{57/80}$), and no resolution of the surviving core is known.

Background

Every integer $n$ has an expansion $n=\sum_{i\ge 0}n_iq^i$ in an integer base $q\ge 2$ with digits $n_i\in\{0,\dots,q-1\}$. Fix a digit $a_0$ and remove it from the alphabet: the set $\mathcal A=\{\sum_{i\ge 0}n_iq^i:\ n_i\in\{0,\dots,q-1\}\setminus\{a_0\}\}$ of integers whose base-$q$ expansion never uses $a_0$ is the standard example of an arithmetically thin set: it has exactly $(q-1)^k$ elements below $q^k$, i.e. about $X^{\log(q-1)/\log q}=X^{1-\epsilon_q}$ elements below $X$ with $\epsilon_q=\log(q/(q-1))/\log q>0$, so it has zero asymptotic density and no multiplicative structure to exploit. The basic distribution theory of such sets is classical: Konyagin and Erdős-Mauduit-Sárközy proved equidistribution of missing-digit sets in residue classes, and Dartyge-Mauduit showed by sieve methods that the missing-digit set contains integers with at most two prime factors. Whether such a sparse set actually contains infinitely many primes was a well-known open question, part of the broader program on digital properties of primes that includes Gelfond's problem on the sum of digits of primes (solved by Mauduit and Rivat) and Bourgain's theorem that one may prescribe a positive proportion of the binary digits of infinitely many primes; Swaenepoel later handled primes with a positive proportion of preassigned digits in any base.

Prime counts are conveniently weighted by the von Mangoldt function $\Lambda(n)=\log p$ when $n$ is a power of a prime $p$ and $0$ otherwise, which turns 'primes occur with density $1/\log n$' into an exact expected value. The natural conjecture for a single excluded digit is an asymptotic with main term $\kappa_q(a_0)(q-1)^k$, where the explicit constant $\kappa_q(a_0)$ (equal to $q/(q-1)$ if the digit shares a factor with $q$, and $q(\phi(q)-1)/((q-1)\phi(q))$ otherwise, with $\phi$ Euler's totient function) records the local congruence information. The source paper - Maynard's 'Primes and Polynomials With Restricted Digits' (preprint 2015, published as Int. Math. Res. Not. 2022) - proved this for all $q>2{,}000{,}000$: for every $A>0$ the error is $O_A((q-1)^k/(\log q^k)^A)$ (Theorem 1.1). The proof applies the circle method: the weighted prime count over $\mathcal A$ is rewritten as an integral pairing the Fourier transform of the prime indicator with that of $1_{\mathcal A}$; frequencies near rationals with small denominator ('major arcs') produce the main term through the distribution of primes in arithmetic progressions, while the complementary 'minor arcs' must be shown to contribute negligibly. That this binary (effectively two-variable) circle method succeeds at all is the surprise: for a generic sparse set one expects only square-root cancellation $\widehat{1_{\mathcal A}}(\theta)\ll\#\mathcal A^{1/2}$, which is far too weak. Maynard's key discovery is that the digit-restricted Fourier transform factorizes over digit positions and exhibits better-than-square-root cancellation on average, quantified by the constant $\alpha_q=\log(C_q\cdot\frac{q}{q-1}\cdot\log q)/\log q$ (with $C_q\in[1/\log q,1+3/\log q]$ the explicit constant from the $L^1$ bound for the digit-restricted Fourier transform); the condition $\alpha_q<1/5$ - satisfied for $q>2{,}000{,}000$ by the numerical bound $\alpha_q<0.198$ - makes the minor arcs negligible once combined with the classical $x^{4/5}$-type bound for exponential sums over primes.

The paper proves two analogues. Theorem 1.2 concerns polynomial values: if $P\in\mathbb Z[X]$ has degree $r$ and lead coefficient $a_r$, and satisfies the necessary local conditions - encoded by a limiting density $\mathfrak S(P)$ of compatible $q$-adic digit patterns, computable by Hensel lifting (the lifting of solutions of congruences modulo prime powers) - then $\sum_{P(n)<q^k}1_{\mathcal A}(P(n))$ equals $a_r^{1/r}\mathfrak S(P)\,q^{k/r}(q-1)^k/q^k$ up to a relative error $O((\log q^k)^{-A})$, provided $q>\exp(\exp(2r))$. This doubly exponential constraint comes from Weyl-differencing bounds for Weyl sums (exponential sums $\sum e(P(n)\theta)$ with polynomial phase), which lose factors exponential in the degree. Theorem 1.3 allows several excluded digits: excluding a set $\{b_1,\dots,b_s\}$ of $s$ digits, the expected asymptotic holds whenever $s<q^{1/5-\epsilon}$ (distinct digits), or $q-s\ge q^{4/5+\epsilon}$ when the excluded digits are consecutive; the $4/5$ exponent reflects the same $x^{4/5}$ barrier for prime exponential sums.

The source itself records that none of these ranges is believed sharp, and anticipates the improvements. In its own words: 'a more involved calculation shows that $q>2500$ is sufficient by the same method, whilst it appears that the method of bilinear sums, Harman's sieve and zero density estimates all have the potential to show the existence of primes missing digits when the base is noticeably smaller. One might conjecture that the result would remain true for all $q>2$.' (The literal conjecture has a single degenerate instance: in base $3$, excluding the digit $1$ leaves only the even digits $0$ and $2$, so every element of the set is even and the only prime in it is $2$; for every base $q\ge 4$ the allowed digits always contain a digit coprime to $q$ and, for every prime $\ell$, a digit not divisible by $\ell$, so no local obstruction of this kind arises.) Harman's sieve is a refinement of the combinatorial sieve that replaces unconditional averages over primes by bilinear 'Type I' sums $\sum_d a_d\sum_m 1_{\mathcal A}(dm)$ and 'Type II' sums $\sum_{m\sim M}\alpha_m\sum_{n\sim N}\beta_n 1_{\mathcal A}(mn)$ with bounded coefficients, estimated here through the digital Fourier structure; zero-density estimates bound how many zeros a family of Dirichlet $L$-functions can share near $s=1$. The remarks after Theorems 1.2 and 1.3 similarly anticipate stronger Vinogradov-type bounds for the Weyl sums (in place of Weyl differencing) for the polynomial range, and Type I-II estimates with Harman's sieve for the multi-digit density thresholds. The paper also notes its error terms are ineffective - they depend on constants that could be spoiled by Siegel zeros, i.e. real zeros of Dirichlet $L$-functions exceptionally close to $s=1$ that make primes-in-arithmetic-progression estimates non-uniform - while indicating that, since only highly composite moduli arise, effective replacements of size $O((q-1)^k\exp(-ck^{1/2}))$ should be possible.

The anticipated 'noticeably smaller base' program was in fact begun by Maynard himself in a second paper, 'Primes with restricted digits' (Inventiones 2019), which developed exactly the Type I/II plus Harman-sieve route: for every digit $a_0\in\{0,\dots,9\}$ there are infinitely many primes with no digit $a_0$ in their decimal expansion, with the correct order of magnitude $\#\mathcal A/\log X$ but not the conjectured asymptotic; the asymptotic formula for one excluded digit holds for $q\ge 12$; and for general bases one may exclude up to $s\le q^{23/80}$ digits (any excluded set), or, when the excluded set is $\{0,\dots,s-1\}$ or $\{q-s,\dots,q-1\}$, in the wider range $s\le q-q^{57/80}$, with asymptotic formulae in the sub-ranges $s\le q^{1/4-\delta}$ and $s\le q-q^{3/4+\delta}$. That paper states explicitly that its methods are 'not powerful enough to show the existence of infinitely many primes with two digits not appearing in their decimal expansion'. Thus the quantitative ranges have been pushed dramatically - and the Harman-sieve route the source anticipated is exactly what worked - but the original conjectural endpoint (every base $q\ge 3$) remains unproven for the bases $3\le q\le 9$ and $q=11$, the base-10 asymptotic remains open, and the polynomial-degree and effectivity directions of the source remain untouched.

Problem Statement

Determine the true quantitative range of Maynard's digit-restriction theorems for primes and polynomial values - the minimal base, the maximal number of excluded digits, the minimal base-versus-degree law, and effective error terms - matching the conjectural endpoints that the source paper itself articulates. The four components below relax quantitative constraints of one and the same circle-method theorem family and are independent, with the conjecturally correct range for each component as their common objective.

(1) Base range, single excluded digit. Let $q\ge 3$, $a_0\in\{0,\dots,q-1\}$, and $\mathcal A$ be the set of integers with no digit $a_0$ in their base-$q$ expansion. Write $\Lambda(n)$ for the von Mangoldt function ($\Lambda(n)=\log p$ when $n$ is a power of a prime $p$, and $0$ otherwise) and $\phi$ for Euler's totient function. Prove (or disprove) Maynard's conjecture that for every base $q\ge 3$ and every digit $a_0$ for which $\mathcal A$ is not locally obstructed,

$$\sum_{n<q^k}\Lambda(n)\mathbf{1}_{\mathcal A}(n)=\kappa_q(a_0)(q-1)^k+O_A\left(\frac{(q-1)^k}{(\log q^k)^A}\right)$$

holds for every $A>0$, where the local constant is $\kappa_q(a_0)=q/(q-1)$ if $(a_0,q)\ne 1$ and $\kappa_q(a_0)=q(\phi(q)-1)/((q-1)\phi(q))$ if $(a_0,q)=1$. The local obstructions are the instances in which every element of $\mathcal A$ is divisible by some prime from a fixed finite set and hence $\mathcal A$ contains only boundedly many primes: if the allowed digits contain none coprime to $q$, every element shares a prime factor with $q$ through its last digit; and if a single prime divides every allowed digit, every element is divisible by that prime. For a single excluded digit the unique obstructed instance with $q\ge 3$ is $(q,a_0)=(3,1)$: the allowed digits $\{0,2\}$ are then all even, so every element of $\mathcal A$ is even and the only prime in $\mathcal A$ is $2$; for every $q\ge 4$ the allowed digits contain a digit coprime to $q$ and, for every prime $\ell$, a digit not divisible by $\ell$, so no local obstruction arises. Currently the asymptotic is known for $q\ge 12$ and the weaker infinitude/order-of-magnitude statement for $q=10$; the open instances are the bases $q\in\{4,5,6,7,8,9,11\}$ together with the digits $a_0\in\{0,2\}$ in base 3, and the conjectured asymptotic formula in base 10 (only the correct order of magnitude is known there, blocked by missing Type II information).

(2) Multiple excluded digits. Determine the density threshold: for which $s=s(q)$ and which excluded digit sets $B\subset\{0,\dots,q-1\}$ with $\#B=s\ge 2$ does the set of integers using no digit of $B$ contain infinitely many primes, and when does the expected asymptotic hold? The statement is subject to the necessary local conditions: the allowed digit set $\{0,\dots,q-1\}\setminus B$ must contain a digit coprime to $q$ (otherwise every element of the set is divisible, through its last digit, by some prime dividing $q$, leaving only boundedly many primes), and no prime may divide every allowed digit (otherwise every element is divisible by that prime). Known: infinitude for $s\le q^{23/80}$ (any $B$) and $q-s\ge q^{57/80}$ ($B=\{0,\dots,s-1\}$ or $\{q-s,\dots,q-1\}$); asymptotics for $s\le q^{1/4-\delta}$ and $s\le q-q^{3/4+\delta}$, and in the source paper $s<q^{1/5-\epsilon}$ / $q-s\ge q^{4/5+\epsilon}$. Open: the full characterization for every admissible excluded set $B$ with $\#B\ge 2$ - whether the restricted set contains infinitely many primes, and whether it satisfies the expected asymptotic - conjecturally limited only by the local congruence obstructions and the nondegeneracy condition $q-s\ge 2$; the characterization is asked in particular for the structured ranges $B=\{0,\dots,s-1\}$ and $B=\{q-s,\dots,q-1\}$, and for the case of two excluded digits in base $q=10$. Here "the expected asymptotic" is the multi-digit analogue of the single-digit display in component (1): with $\mathcal A_B$ the set of integers using no digit of $B$ and $s'=\#\{b\in B:(b,q)=1\}$ the number of excluded digits coprime to $q$, it is $\sum_{n<q^k}\Lambda(n)\mathbf{1}_{\mathcal A_B}(n)=\frac{q(\phi(q)-s')}{(q-s)\phi(q)}(q-s)^k+O_A\left(\frac{(q-s)^k}{(\log q^k)^A}\right)$ for every $A>0$, asserted for $q-s\ge 2$; the degenerate alphabet $q-s=1$ (a single allowed digit, e.g. $q=3$ and $B=\{0,2\}$) has a bounded main term and no such asymptotic is claimed there, and its infinitude question - whether there are infinitely many primes of the form $(q^k-1)/(q-1)$ (base-$q$ repunits), an unrelated classical problem - is outside this component and is not required. Decide, for every base $q\ge 3$ and every admissible excluded set $B$ with $\#B\ge 2$ and $q-s\ge 2$, both of these questions; the largest $s$ per base and the extremal excluded sets then follow from that per-$B$ decision.

(3) Polynomial values. For a degree-$r$ polynomial $P\in\mathbb Z[X]$ with lead coefficient $a_r$ and $\mathfrak S(P)>0$, where

$$\mathfrak S(P)=\lim_{J\to\infty}\frac{\#\{(n,m):0\le n,m<q^J,\ m\in\mathcal A,\ P(n)\equiv m\bmod q^J\}}{(q-1)^J}$$

is the limiting density of $q$-adically compatible digit patterns (computable by Hensel lifting, and positive exactly when the local solubility conditions hold), improve the requirement $q>\exp(\exp(2r))$ toward the information-theoretic limit: the main term $q^{k/r}(q-1)^k/q^k$ exceeds $1$ only once $\log(q/(q-1))/\log q<1/r$, i.e. roughly $q\log q\gtrsim r$, so the conjecturally necessary growth is essentially linear in $r$; determine how small $q$ can be taken as a function of $r$. Determine the correct base-versus-degree law, closing the gap to the conjecturally necessary, essentially linear growth $q\log q\gtrsim r$ (up to explicitly stated constants).

(4) Effective error terms. Replace the ineffective constants (arising from possible Siegel zeros in the primes-in-arithmetic-progressions input) by explicit effective ones in all regimes of the above theorems (components (1)-(3), corresponding to the source's Theorems 1.1-1.3), as the source indicates should be possible because only highly composite moduli arise. The target error shape is the source's sketched effective $O((q-1)^k\exp(-ck^{1/2}))$ for an explicit $c>0$.

References

1. James Maynard, Primes and polynomials with restricted digits, Int. Math. Res. Not. IMRN 2022 (2022), no. 14, 10626-10648, DOI 10.1093/imrn/rnab002, https://doi.org/10.1093/imrn/rnab002; preprint arXiv:1510.07711 (2015), https://arxiv.org/abs/1510.07711
2. James Maynard, Primes with restricted digits, Invent. Math. 217 (2019), no. 1, 127-218, DOI 10.1007/s00222-019-00865-6, https://doi.org/10.1007/s00222-019-00865-6; preprint arXiv:1604.01041 (2016), https://arxiv.org/abs/1604.01041
3. James Leng and Mehtaab Sawhney, Vinogradov's Theorem for Primes With Restricted Digits, Int. Math. Res. Not. IMRN 2025 (2025), no. 3, DOI 10.1093/imrn/rnae294, https://doi.org/10.1093/imrn/rnae294; preprint arXiv:2409.06894, https://arxiv.org/abs/2409.06894
4. Kunjakanan Nath, Primes with a missing digit: Distribution in arithmetic progressions and an application in sieve theory, J. Lond. Math. Soc. 109 (2024), no. 1, DOI 10.1112/jlms.12837, https://doi.org/10.1112/jlms.12837; preprint arXiv:2108.09212, https://arxiv.org/abs/2108.09212
5. Kyle Pratt, Primes from sums of two squares and missing digits, Proc. Lond. Math. Soc. (3) 120 (2020), no. 6, 770-830, DOI 10.1112/plms.12307, https://doi.org/10.1112/plms.12307; preprint arXiv:1806.02699, https://arxiv.org/abs/1806.02699
6. Cathy Swaenepoel, Prime numbers with a positive proportion of preassigned digits, Proc. Lond. Math. Soc. (3) 121 (2020), no. 1, 83-151, DOI 10.1112/plms.12314, https://doi.org/10.1112/plms.12314
7. Ben Green, Waring's problem with restricted digits, Compos. Math. 161 (2025), no. 2, 341-364, DOI 10.1112/s0010437x24007723, https://doi.org/10.1112/s0010437x24007723
8. Andrew Granville, Missing digits and good approximations, Bull. Amer. Math. Soc. (N.S.) 61 (2024), no. 1, 23-53 (published electronically October 2023), DOI 10.1090/bull/1811, https://doi.org/10.1090/bull/1811; preprint arXiv:2308.03126, https://arxiv.org/abs/2308.03126
9. Mengyao Jing, Huaning Liu and Jingyue Li, Bounds for exponential sums over integers with restricted digits, Ramanujan J. 69 (2026), no. 4, DOI 10.1007/s11139-026-01380-y, https://doi.org/10.1007/s11139-026-01380-y
10. Helmut Maier and Michael Th. Rassias, The ternary Goldbach problem with two Piatetski-Shapiro primes and a prime with a missing digit, Commun. Contemp. Math. 25 (2023), no. 2 (published online October 2022), DOI 10.1142/s0219199721501017, https://doi.org/10.1142/s0219199721501017; preprint arXiv:2006.07873, https://arxiv.org/abs/2006.07873
11. Kannan Soundararajan, The work of James Maynard, arXiv:2207.03463 (2022), https://arxiv.org/abs/2207.03463
12. Jean Bourgain, Prescribing the binary digits of primes, II, Israel J. Math. 206 (2015), no. 1, 165-182, DOI 10.1007/s11856-014-1129-5, https://doi.org/10.1007/s11856-014-1129-5
13. Christian Mauduit and Joël Rivat, Sur un problème de Gelfond : la somme des chiffres des nombres premiers, Ann. of Math. (2) 171 (2010), no. 3, 1591-1646, DOI 10.4007/annals.2010.171.1591, https://doi.org/10.4007/annals.2010.171.1591
14. Cécile Dartyge and Christian Mauduit, Nombres presque premiers dont l'écriture en base r ne comporte pas certains chiffres, J. Number Theory 81 (2000), no. 2, 270-291, DOI 10.1006/jnth.1999.2458, https://doi.org/10.1006/jnth.1999.2458
15. Sergei Konyagin, Arithmetic properties of integers with missing digits: distribution in residue classes, Period. Math. Hungar. 42 (2001), no. 1-2, 145-162, DOI 10.1023/a:1015256809636, https://doi.org/10.1023/a:1015256809636
16. Paul Erdős, Christian Mauduit and András Sárközy, On arithmetic properties of integers with missing digits II: Prime factors, Discrete Math. 200 (1999), no. 1-3, 149-164, DOI 10.1016/s0012-365x(98)00331-8, https://doi.org/10.1016/s0012-365x(98)00331-8