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!

  • 1
    $\begingroup$ Try a random set: include each $n$ in $S$ independently with a probability chosen to make the density work out. $\endgroup$ – Ben Barber Apr 17 '14 at 15:14
  • 1
    $\begingroup$ 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$). $\endgroup$ – Aaron Meyerowitz Apr 17 '14 at 15:16
  • 1
    $\begingroup$ 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. $\endgroup$ – Aaron Meyerowitz Apr 17 '14 at 15:51
  • 1
    $\begingroup$ See : mathoverflow.net/questions/163407/… The answer of Prof. Quas provides an example. $\endgroup$ – 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}$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.