# Existence of a certain subset of natural numbers equidistributed modulo $m$ for every $m$

I was talking to a friend and the following set $S$ came up.

Let $f$ be some real valued function tending to infinity. Let $S$ be a subset of natural numbers such that $|S \cap [1,N]| = N^{\delta}+ O(N^{\delta}/f(N))$ and further for any $r,m \in \mathbb{N}$ we have $$| \{ x \in S \cap [1,N] : x \equiv r (\text{mod }m) \}| = \frac1m N^{\delta}+ O(N^{\delta}/f(N)),$$ where the implicit constant does not depend on $r,m$.

I was curious are there any examples of such set $S$ other than the set of all natural numbers, which would satisfy this condition when $\delta=1$? I am also wondering is it reasonable to assume such a set exist for $\delta<1$ with some choice of $f$? Thanks!

• Try a random set: include each $n$ in $S$ independently with a probability chosen to make the density work out. – Ben Barber Apr 17 '14 at 15:14
• The first condition alone , with $\delta=1$, says that the number of non-members in $[1,N]$ goes to $0$ as a proportion. I'm sure you can come up with examples. Then the $\mod m$ condition must also hold (this is special to $\delta=1$). – Aaron Meyerowitz Apr 17 '14 at 15:16
• If you were trying for $\delta=1/2$ then the set of squares would satisfy the first condition but not the $\mod m$ conditions. I'd suspect that taking the integer part (or rounded value) of $\{{k^{1/\delta} : k \in \mathbb{N}\}}$ does work as long as $1/\delta$ is not an integer. When it is (so $1/\delta \ge 2$) then some perturbation such as the integer part of part of $n^{1/\delta}+n^{3/2}$ might well work. – Aaron Meyerowitz Apr 17 '14 at 15:51
• See : mathoverflow.net/questions/163407/… The answer of Prof. Quas provides an example. – user39115 Apr 17 '14 at 16:52

As mentioned by Aaron Meyerowitz, a set of the form $$S=\left\{\left[k^{1/\gamma}\right]:\ k\in\mathbb{N}\right\}$$ should work for any $1/2<\gamma<1$. Notice that for such a value of $\gamma$, $$\left[(k+1)^{\gamma}\right]-\left[k^{\gamma}\right]=\begin{cases} 1 & \text{ if }k+1=\left[n^{1/\gamma}\right]\\ 0 & \text{ otherwise} \end{cases}.$$

Let $s(x)=\left\{ x\right\} -\frac{1}{2}.$ Then the counting function for $S$ inside an arithmetic progression is $$\sum_{\begin{array}{c} k\leq x-1\\ k\equiv a\text{ mod }q \end{array}}\left[(k+1)^{\gamma}\right]-\left[k^{\gamma}\right]=\sum_{\begin{array}{c} k\leq x-1\\ k\equiv a\text{ mod }q \end{array}}(k+1)^{\gamma}-k^{\gamma}+\sum_{\begin{array}{c} k\leq x-1\\ k\equiv a\text{ mod }q \end{array}}s(k^{\gamma})-s((k+1)^{\gamma}).$$ Above we have split up the sum into a main term and an error term.

Main Term: By the generalized binomial theorem $$(k+1)^{\gamma}-k^{\gamma}=\gamma k^{\gamma-1}+O\left(k^{\gamma-2}\right),$$ and so $$\sum_{\begin{array}{c} k\leq x-1\\ k\equiv a\text{ mod }q \end{array}}(k+1)^{\gamma}-k^{\gamma}=\gamma\sum_{\begin{array}{c} k\leq x-1\\ k\equiv a\text{ mod }q \end{array}}k^{\gamma-1}+O\left(1\right).$$ As $\gamma<1$, the main term equals $$\sum_{\begin{array}{c} k\leq x-1\\ k\equiv a\text{ mod }q \end{array}}(k+1)^{\gamma}-k^{\gamma}=\frac{x^{\gamma}}{q}+O(1),$$ which satisfies the desired condition as $\sum_{n\leq x} 1_S(n)\sim x^\gamma$.

Error Term: The error term is more difficult to deal with, and in what follows we will give a sketch. The notation is the same as that used in Balog and Friedlander's paper on Piatetski-Shapiro primes.

Recall the Fourier expansion for $s(x).$ We have $$s(x)=-\sum_{0<|h|<T}\frac{1}{2\pi ih}e(hx)+O\left(\min\left(1,\frac{1}{T\|x\|}\right)\right),$$ and $$\min\left(1,\frac{1}{T\|x\|}\right)=\sum_{h=-\infty}^{\infty}b_{h}e(hx)$$ where $$|b_{h}|\ll\min\left(\frac{\log2T}{T},\ \frac{T}{h^{2}}\right).$$ Thus our error term can be written as $\Sigma_{1}+\Sigma_{2}$ where $\Sigma_{1}$ arises from $\sum_{0<|h|<T}\frac{1}{2\pi ih}e(hx),$ and $\Sigma_{2}$ arises from the term $\sum_{h=-\infty}^{\infty}b_{h}e(hx).$ To deal with $\Sigma_{2},$ notice that

$$\left|\sum_{\begin{array}{c} k\leq x-1\\ k\equiv a\text{ mod }q \end{array}}\sum_{h=-\infty}^{\infty}b_{h}e(hk^{\gamma})\right|\leq\left|\sum_{h=-\infty}^{\infty}\left|b_{h}\right|\left|\sum_{\begin{array}{c} k\leq x-1\\ k\equiv a\text{ mod }q \end{array}}e(hk^{\gamma})\right|\right|.$$ An estimate of Van Der Corput yields $$\left|\sum_{k\leq\frac{x}{q}}e(h(qk+a)^{\gamma})\right|\ll h^{1/2}x^{\gamma/2}+h^{-1/2}x^{1-\gamma/2},$$ and so $$\Sigma_{2}\ll\frac{x}{T}+\sum_{h=1}^{\infty}\left|b_{h}\right|\left(h^{1/2}x^{\gamma/2}+h^{-1/2}x^{1-\gamma/2}\right)$$

$$\ll xT^{-1}+T^{1/2}x^{\gamma/2}+T^{-1/2}x^{1-\gamma/2}.$$ It remains to bound $\Sigma_{1}.$ By using the identity $$e(hk^{\gamma})-e(h(k+1)^{\gamma})=2\pi i\gamma h\int_{0}^{1}\left(k+u\right)^{\gamma-1}e\left(h(k+u)^{\gamma}\right)du,$$ $\Sigma_{1}$ is at most $$\Sigma_{1}\ll\sum_{0<|h|<T}\int_{0}^{1}\sum_{\begin{array}{c} k\leq x-1\\ k\equiv a\text{ mod }q \end{array}}\left(k+u\right)^{\gamma-1}e\left(h(k+u)^{\gamma}\right)du.$$ Partial summation along with other classical bounds on exponential sums should be able to handle the problem from here. In the end we will take $T=x^{1-\gamma+\delta}$ for some small $\delta>0$. I believe that we may take $\delta=\frac{1}{4}\left(\gamma-\frac{1}{2}\right)$ to obtain $$\sum_{\begin{array}{c} k\leq x-1\\ k\equiv a\text{ mod }q \end{array}}\left[(k+1)^{\gamma}\right]-\left[k^{\gamma}\right]=\frac{x^\gamma}{q}+O\left(x^{\frac{3}{4}\gamma+\frac{1}{8} }\right).$$

Remark: In the above method the error term grows out of control if $\gamma\leq \frac{1}{2}$.

• Thank you very much for the answer! I greatly appreciate it!! – SJY Apr 17 '14 at 20:36