Dartyge’s talk on ellipsephic integers

Posted by: matheuscmss | December 22, 2019

Dartyge’s talk on ellipsephic integers

Last November, I attended the beautiful conference Prime Numbers, Determinism and Pseudorandomness at CIRM. This conference was originally prepared to celebrate the 60th birthday of Christian Mauduit, but unfortunately a tragic event during the summer of 2019 made that this conference ended up becoming a celebration of the memory of Christian.

The links to the titles, abstracts, slides and videos for the talks of this excellent meeting can be found here.

In this blog post, I would like to transcript my notes for the amazing survey talk “On ellipsephic integers” by Cécile Dartyge on one of Christian’s favorite topics in Analytic Number Theory, namely, the statistics of integers missing some digits.

Of course, all mistakes in the sequel are my sole responsibility.

1. Introduction

Ellipsephic integers refers to a collection of integers with missing digits in a certain basis (e.g., all integers whose representation in basis 10 doesn’t contain the digit 9). Christian Mauduit proposed this nomenclature partly because ellipsis = missing and psiphic = digit in Greek.

Formally, we consider a basis ${r\in\mathbb{N}}$ , ${r\geq 3}$ , and a subset ${\mathcal{D}}$ of ${\{0, 1, \dots, r-1\}}$ of cardinality ${2\leq\#\mathcal{D}\leq r-1}$ . The corresponding set of ellipsephic integers ${W_{\mathcal{D}}}$ is

$\displaystyle W_{\mathcal{D}}:=\left\{n=\sum\limits_{j=0}^k a_j r^j: a_j\in\mathcal{D} \, \, \,\forall\,1\leq j\leq k\right\}.$

The subset of ellipsephic integers below a certain threshold ${x}$ is denoted by

$\displaystyle W_{\mathcal{D}}(x):=\{n\in W_{\mathcal{D}}: n< x\}.$

For the sake of exposition, we shall assume from now on that ${0\in\mathcal{D}}$ and

$\displaystyle gcd(d\in\mathcal{D})=1$

unless it is explicitly said otherwise.

2. Ellipsephic integers on arithmetic progressions

Let ${W_{\mathcal{D}}(x,a,q) := \{n\in W_{\mathcal{D}}(x): n\equiv a \, (\textrm{mod } q)\}}$ . Despite their sparseness, it was proved by Erdös, Mauduit and Sárközy that ellipsephic integers behave well (i.e., “à la Siegel-Walfisz”) along arithmetic progressions:

Theorem 1 (Erdös–Mauduit–Sárközy) There are two constants ${c_1=c_1(r,\mathcal{D})}$ and ${c_2=c_2(r,\mathcal{D})}$ such that

$\displaystyle \left|\#W_{\mathcal{D}}(x,a,q)-\frac{\#W_{\mathcal{D}}(x)}{q}\right|\ll_{r,\mathcal{D}}\frac{\#W_{\mathcal{D}}(x)}{q}\exp\left(-c_2\frac{\log x}{\log q}\right)$

for all ${a\in\mathbb{N}}$ , ${gcd(q,r(r-1))=1}$ , ${q\leq \exp(c_1\sqrt{\log x})}$ and ${x}$ sufficiently large.

Proof: As it is usual in this kind of counting problem, one relies on exponential sums. More precisely, note that

$\displaystyle \#W_{\mathcal{D}}(x,a,q) = \frac{1}{q}\sum\limits_{h=1}^q\sum\limits_{n\in W_{\mathcal{D}}(x)} e\left(\frac{h(n-a)}{q}\right)$

where ${e(t):=\exp(2\pi i t)}$ . The “main term” ${\#W_{\mathcal{D}}(x)/q}$ comes from the case ${h=q}$ , so that our task consists into estimating the “error term”. For this sake, one has essentially to study

$\displaystyle F_{N,\mathcal{D}}(h/q):=\sum\limits_{n\in W_{\mathcal{D}}(x)} e\left(\frac{hn}{q}\right)$

where ${x:=r^N}$ . Observe that

$\displaystyle F_{N,\mathcal{D}}(h/q)=\prod\limits_{j=1}^{N-1}\left(\sum\limits_{d\in\mathcal{D}}e\left(\frac{hdr^j}{q}\right)\right):=\prod\limits_{j=1}^{N-1} u_{\mathcal{D}}(hr^j/q).$

The terms ${u_{\mathcal{D}}(hr^j/q)}$ are controlled thanks to the following lemma (giving some saving over the trivial bound ${|u_{\mathcal{D}}(\alpha)|\leq \#\mathcal{D}}$ for all ${\alpha\in\mathbb{R}}$ ):

Lemma 2 (Erdös–Mauduit–Sárközy) Let ${t:=\#\mathcal{D}}$ . For any ${\alpha\in\mathbb{R}}$ , one has

$\displaystyle |u_{\mathcal{D}}(\alpha)|\leq t\left(1-\frac{\|\alpha\|^2}{(r-1)^5}\right)$

where ${\|\alpha\|:=\min\limits_{n\in\mathbb{Z}}|\alpha-n|}$ .

In order to take full advantage of the saving on the right-hand side of the inequality, one needs the following lemma:

Lemma 3 (Mauduit–Sárközy) For any ${\beta\in\mathbb{R}}$ and ${q\leq r^{(N-8)/2}}$ , one has

$\displaystyle \sum\limits_{0\leq k<N}\left\|\beta+\frac{hr^k}{q}\right\|\geq \frac{(r-1)^2}{128}\frac{N}{\log q}$

The details of the derivation of the desired theorem from the two lemmas above is explained in Section 4 of Erdös–Mauduit–Sárközy paper. $\Box$

The methods of Erdös–Mauduit–Sárközy above paved the way to further results about ellipsephic integers. For instance, similarly to Bombieri–Vinogradov theorem, it is natural to expect that the distribution result of Erdös–Mauduit–Sárközy gets better on average: as it turns out, this was done independently by C. Dartyge and C. Mauduit, and S. Konyagin (circa 2000):

Theorem 4 (Dartyge–Mauduit, Konyagin) There exists ${\alpha=\alpha(r,t)>0}$ such that for all ${B>0}$ there exists ${A>0}$ with the property that

$\displaystyle \sum\limits_{\substack{q\leq x^{\alpha}/(\log x)^A,\\ \textrm{gcd}(q,r(r-1))=1}}\left|\#W_{\mathcal{D}}(x,a,q)-\frac{\#W_{\mathcal{D}}(x)}{q}\right|\ll \frac{\#W_{\mathcal{D}}(x)}{(\log x)^B}.$

Proof: One uses Lemmas 2 and 3 above, a large sieve method, and some bounds on the moments

$\displaystyle \int_0^1 |F_{N,\mathcal{D}}(s)|^m \, ds$

of the function ${F_{N,\mathcal{D}}}$ . $\Box$

Remark 1 More recently, K. Aloui, C. Mauduit and M. Mkaouar improved (in 2017) some of the results of Erdös–Mauduit–Sárközy to obtain some distribution results for ellipsephic and palindromic integers.

3. Ellipsephic primes and almost primes

By pursuing sieve methods, Dartyge and Mauduit obtained in 2001 the following result about ellipsephic almost primes:

Theorem 5 (Dartyge–Mauduit) There exists ${k=k(r, t)\in\mathbb{N}}$ such that

$\displaystyle \#\{n\in W_{\mathcal{D}}(x): \Omega(n)\leq k\}\gg\frac{\#W_{\mathcal{D}}(x)}{\log x},$

where ${\Omega(n)}$ stands for the number of prime factors of ${n}$ (counted with multiplicity).

A natural question motivated by this theorem concerns the determination of explicit values of ${k}$ in the previous statement. The answer to this question is somewhat related to the value of ${\alpha}$ in the last theorem of the previous section and, in this direction, it is possible to show that

if , then one can take
- ${k=3}$ (and ${\alpha\sim1/3}$ ) for ${r=3}$ ,
- ${k=5}$ (and ${\alpha\sim 1/4}$ ) for ${r=4}$ , …,
- ${k=23}$ for ${r=10}$ , and
- ${k=\frac{8}{\pi}(1+o(1))r}$ as ${r\rightarrow\infty}$
if ${\mathcal{D}=\{0,\dots,r-2\}}$ , ${r\geq 5}$ , then one can take ${k=2}$ .

In 2009 and 2010, C. Mauduit and J. Rivat proved two conjectures of Gelfond on sums of digits of primes and squares. The methods in these articles gave hope to reach the case ${k=1}$ (of ellipsephic primes) in Dartyge–Mauduit theorem above. This was recently accomplished by J. Maynard in 2016: if ${\mathcal{D}=\{0,\dots,r-1\}\setminus\{a_0\}}$ and ${r\geq 10}$ , then

$\displaystyle \#\{p\in W_{\mathcal{D}}(x): p \textrm{ prime}\}\gg \frac{\#W_{\mathcal{D}}(x)}{\log x}$

Remark 2 In his thesis, A. Irving got analogous results for palindromic ellipsephic integers with ${3}$ digits in basis ${r\geq 4}$ with two prime factors.

After this brief discussion of ellipsephic almost primes, let us now talk about ellipsephic integers possessing only small prime factors.

4. Friable ellipsephic integers

Recall that a friable integer is an integer without large prime factors. For later reference, we denote the largest prime factor of ${n}$ by

$\displaystyle p^+(n):=\max\limits_{\substack{p|n\\p\textrm{ prime}}} p.$

It was shown by Erdös–Mauduit–Sárközy that, for any fixed ${a\in\mathcal{D}\setminus\{0\}}$ and for all ${\varepsilon>0}$ , there are infinitely many ellipsephic integers ${n\in W_{\mathcal{D}}}$ of the form ${n=\sum\limits_{i=0}^{k-1}ar^i}$ whose largest prime factor is ${p^+(n)\leq n^{\varepsilon}}$ .

Logically, this results motivates the question to establish the existence of a positive proportion of friable ellipsephic integers. This seems a hard task for arbitrary ${\varepsilon>0}$ , but this problem becomes more tractable for small values of ${\varepsilon}$ when the basis ${r}$ is large enough.

In fact, S. Col showed that there exists ${0<\alpha=\alpha(r,\mathcal{D})<1}$ such that

$\displaystyle \#\{n\in W_{\mathcal{D}}(x): p^+(n)<n^{\alpha}\}\gg\#W_{\mathcal{D}}(x).$

Moreover, if ${\mathcal{D}=\{0,1\}}$ , then it is possible to take ${\alpha=1-\frac{\pi}{4r}\left(1-\frac{3\pi}{4r}\right)}$ (which is close to one for ${r}$ large). On the other hand, ${\alpha}$ can be taken very small when ${\mathcal{D}=\{0,\dots,r-1\}\setminus\{a_0\}}$ and ${r}$ sufficiently large.

5. Ellipsephic solutions to Vinogradov systems

A Vinogradov system is a system of equations on the variables ${x_1,\dots, x_s, y_1, \dots, y_s}$ of the form:

$\displaystyle x_1^j+\dots+x_s^j = y_1^j+\dots+y_s^j, \quad 1\leq j\leq k.$

A major breakthrough on counting solutions to Vinogradov systems was famously obtained by J. Bourgain, C. Demeter and L. Guth (see also the text and the video of L. Pierce’s Bourbaki seminar talk on this subject).

Concerning ellipsephic solutions to Vinogradov systems (i.e., solutions with ${x_i, y_i\in W_{\mathcal{D}}}$ for all ${1\leq i\leq s}$ ), Kirsty Briggs showed that for ${k=2}$ , ${r=p}$ prime and ${\mathcal{D}=\{d^2: d<\sqrt{p}\}}$ , the trivial bound ${\leq \#W_{\mathcal{D}}(x)^{2s}}$ on the number of solutions of the Vinogradov system

$\displaystyle x_1+\dots+ x_s=y_1+\dots+y_s,$

$\displaystyle x_1^2+\dots+x_s^2=y_1^2+\dots+y_s^2$

with ${x_i, y_i\in W_{\mathcal{D}}(x)}$ can be improved into ${\ll_{\varepsilon} \#W_{\mathcal{D}}(x)^{2s-6+\varepsilon}}$ ${\forall \,\varepsilon>0}$ whenever ${s\geq 6}$ . (In particular, this result is saying that in the case ${s=6}$ , the main contribution to the number of ellipsephic solutions of the corresponding Vinogradov system comes from the trivial solutions ${x_i=y_i\in W_{\mathcal{D}}(x)}$ .)

6. Ellipsephic numbers in finite fields

The notion of finite-field analogs of ellipsephic numbers was studied by several authors including Dartyge, Mauduit and Sárközy.

In order to explain some results in this direction, let us setup some notations. Let ${q=p^r}$ be the power of a prime number ${p}$ and denote by ${z\in \mathbb{F}_q}$ a primitive element generating a basis ${\mathcal{B}=\{1,z,\dots, z^{r-1}\}}$ of ${\mathbb{F}_q}$ over ${\mathbb{F}_p}$ . In this way, we can represent a number ${x\in\mathbb{F}_q}$ as

$\displaystyle x=\sum\limits_{i=0}^{r-1} c_i z^i \quad \textrm{ with }0\leq c_i<p.$

Given a set of digits ${\mathcal{D}\subset\{0,\dots, p-1\}}$ with ${2\leq \#\mathcal{D}\leq p-1}$ , the associated subset of ellipsephic numbers is

$\displaystyle W_{\mathcal{D}}:=\left\{\sum\limits_{i=0}^{r-1} c_iz^i: c_i\in\mathcal{D} \,\,\,\forall\, 0\leq i\leq r-1\right\}$

Given a polynomial ${f(x)\in\mathbb{F}_q[x]}$ , we can study the set of its ellipsephic values via the set

$\displaystyle W_{\mathcal{D}}(f):=\{a\in\mathbb{F}_q: f(a)\in W_{\mathcal{D}}\}.$

The size of ${W_{\mathcal{D}}(f)}$ is described by the following theorem:

Theorem 6 (Dartyge–Mauduit–Sárközy) If ${\textrm{deg}(f)=n}$ , then

$\displaystyle \left|\#W_{\mathcal{D}}(f)-\#W_{\mathcal{D}}\right|\leq \frac{n-1}{\sqrt{q}}\left(\#\mathcal{D}+p\sqrt{p-\#\mathcal{D}}\right)$

This result is specially interesting when ${\mathcal{D}}$ contains a positive proportion of ${\mathbb{F}_p}$ . Moreover, it can be improved when ${\mathcal{D}}$ contains consecutive digits.

More recently, a better result was obtained by R. Dietmann, C. Elsholtz and I. Shparlinski for the case ${f(x)=x^2}$ . Finally, the reader can consult the work of C. Swaenepoel for further results.

Posted in expository, math.NT, Mathematics | Tags: arithmetic progressions, Bombieri-Vinogradov, Cécile Dartyge, Christian Mauduit, CIRM-Marseille, ellipsephic integers, finite fields, friable integers, missing digits, polynomials, primes and almost primes, Siegel-Walfisz, Vinogradov systems

M	T	W	T	F	S	S
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

	Adam on Breuillard-Sert’s joint…
	Adam on Breuillard-Sert’s joint…
	Writing a Hilbert C*… on ERT16: Compact extensions
	matheuscmss on Yoccoz book collection at…
	Jairo B. on Yoccoz book collection at…

Disquisitiones Mathematicae