Polynomialy equidistributed sets
A set $S$ is called polynomialy equidistributed if there exists a $p$ such that for any injective polynomial $p:\mathbb N\to\mathbb N$ $$\lim_{n\to \infty}\frac{|\{s|s\in \mathbb N,s\leq n,f(s)\in S\}| }{n}=\lim_{n\to \infty}\frac{|S\cap f(\{0,1,...,n\})| }{n}=p$$
For example, $\mathbb N$ is PE with $p=1$ as the set's image is always in $\mathbb N$,$\{2^n|n\in\mathbb N\}$ is PE with $p=0$ as the exponential grows faster than any polynomial.
The set $\{2n|n\in\mathbb N\}$ isn't PE as the limit for the polynomial $2n$ is $1$ and for $2n+1$ is $0$.
Questions:
1.is $\{[\sqrt2n]|n\in\mathbb N\}$ PE?($[~~]$ is rounding)
2.does there exist a set PE with $0<p<1$?
Partial answers:
- I've found that $p(n)=(1+\sqrt 2)^n + (1-\sqrt 2)^n$ is always in the set, but isn't a polynomial.
I've managed to prove that for linear functions that the limit converges to $\frac{1}{\sqrt2}$.
The Thue–Morse sequence
I've thought about this sequence, as it seems "random", so it might be PE with $p=0.5$.
using code, I have found something interesting, for $f(n)=3n$ I get $p=0.5$, while, for $f(n)=n^2$ I got $p=0.25$.
For the first question, the answer is yes. This can also lead to a proof of the second question explicitly. The key is the following lemma, sourced from this post.
Lemma. Let $p(n)= \chi n^d + a_{d-1} n^{d-1} + \cdots + a_1 n + a_0$ be any polynomial of positive degree, with $\chi$ irrational. Then $\{p(n)\colon n\in\mathbb N\}$ is equidistributed modulo $1$; that is, for any union $I\subset [0,1)$ of intervals, $$\lim_{n\to\infty}\frac{|\{1\leq k\leq n\mid \{p(k)\}\in I\}|}n=|I|,$$ where $\{x\}=x-\lfloor x\rfloor$ is the fractional part of $x$ and $|I|$ denotes the total length of $I$.
This allows us to prove the following more general proposition.
Proposition. For any irrational $\alpha>1$, the set $S=\{[\alpha n]\colon n\in\mathbb N\}$ is polynomially equidistributed with density $p=1/\alpha$.
Proof. First, define $$I=\left[0,\frac1{2\alpha}\right]\cup\left[1-\frac1{2\alpha},1\right)\subset [0,1)$$ with $|I|=1/\alpha$. We see that $n\in S$ if and only if there exists some $m$ with $$\alpha m-\frac12\leq n\leq \alpha m+\frac12,$$ which is equivalent to $$\left\{\frac n\alpha\right\}\in I.$$ Now, pick any polynomial $f\colon \mathbb N\to\mathbb N$, and let $p(n)=f(n)/\alpha$. This is a polynomial of positive degree with irrational leading coefficient, and so our lemma implies that $$\lim_{n\to\infty}\frac{|\{1\leq k\leq n\mid f(k)\in S\}|}n=|I|=\frac1\alpha,$$ as desired.
This proposition is enough to answer the second question for all irrational $p$. For rational $p$ (as far as I can tell) a new approach is needed.
For the second question, we first prove the following lemma.
Lemma. Let $X_1,X_2,\dots$ be independent random $0$-$1$ variables, let $0<p<1$, and let $\epsilon>0$. Then, there exists some positive integer $N=N(p,\epsilon)$ depending only on $p$ and $\epsilon$ such that $$\Pr\big[\text{there exists }n>N\text{ with }\big|(X_1+\cdots+X_n)-pn\big|>pn^{3/4}\big]<\epsilon.$$
Proof. We'll first bound $$\Pr\big[\big|(X_1+\cdots+X_n)-pn\big|>pn^{3/4}\big]$$ given $n$. Recall the Chernoff bound, which states that if $X$ is a random variable which is the sum of independent $0$-$1$ random variables with $\mathbb E[X]=\mu$, and $\delta>0$, then $$\Pr\big[|X-\mu|>\delta\mu\big]\leq 2e^{-\frac{\delta^2\mu}3}.$$ Applying this to our case with $X=X_1+\cdots+X_n$, $\mu=pn$, and $\delta=n^{-1/4}$ gives $$\Pr\big[\big|(X_1+\cdots+X_n)-pn\big|>pn^{3/4}\big]\leq 2e^{-\frac{p^{-1}n^{1/2}}3}.$$ Note that $$\sum_{n=1}^\infty 2e^{-\frac{pn^{1/2}}3}$$ converges, by limit comparison with, e.g., $1/n^2$. This means that there exist some $N$ for which $$\sum_{n=N+1}^\infty 2e^{-\frac{pn^{1/2}}3}<\epsilon.$$ Taking this $N$ implies the desired result, by the union bound.
Fix some $0<p<1$. We claim that, if each integer $n$ is placed into $S$ with probability $p$ and excluded with probability $1-p$, independently, then $S$ is polynomially equidistributed with probability $1$. We'll show that $S$ is polynomially equidistributed with probability at least $1-\eta$ for any $\eta>0$.
Enumerate the injective polynomials $f:\mathbb N\to\mathbb N$ as $f_1,f_2,\dots$ (there are countably many of them, so this can be done). Let $\epsilon_i=\eta 2^{-i}$ for each $i\geq 1$, so that $$\sum_{i=1}^\infty \epsilon_i=\eta.$$ We'll show that the probability that $S$ fails to be equidistributed with respect to $f_i$ is at most $\epsilon_i$, which will imply the desired result by the union bound.
For each $i,n\geq 1$, let $\mathcal F_i(n)=\{f_i(1),\dots,f_i(n)\}$. Then $S$ is equidistributed with respect to $f_i$ if and only if $$\lim_{n\to\infty}\frac{|S\cap \mathcal F_i(n)|}{n}=p.$$ Now, for $j\geq 1$, let $X_j$ be the event that $f_i(j)\in S$; this happens with probability $p$, and (since $f_i$ is injective) the $X_j$ are all independent from each other. Letting $N_i=N(p,\epsilon_i)$, our lemma implies $$\Pr\big[\text{there exists }n>N_i\text{ with }\big||S\cap \mathcal F_i(n)|-pn|>pn^{3/4}\big]<\epsilon_i.$$ So, with probability at least $1-\epsilon_i$, $$\left|\frac{|S\cap \mathcal F_i(n)|}{n}-p\right|<pn^{-1/4}\text{ for every }n>N_i,$$ and so, since $pn^{-1/4}\to 0$ as $n\to\infty$, $$\lim_{n\to\infty}\frac{|S\cap \mathcal F_i(n)|}{n}=p,$$ as desired. This means that $S$ is equidistributed with respect to $f_i$ with probability at least $1-\epsilon_i$.
So, the probability that there exists some $i\geq 1$ for which $S$ is not equidistributed with respect to $f_i$ is at most $\epsilon_1+\epsilon_2+\cdots=\eta$. This means that $S$ is polynomially equidistributed with probability at least $1-\eta$, as desired.