Problem: Let $c>0$ be a real number, and suppose that for every positive integer $n$, at least one percent of the numbers $1^c,2^c,3^c,\ldots,n^c$ are integers. Prove that $c$ is an integer.

My progress: At first we will deal with the case when $c$ is a rational number. Suppose $c=\frac{a}{b}$. It indeed suffices to prove the statement for rationals of the form $\frac{1}{a}$. Observe that there are $\lfloor{M^{\frac{1}{a}}}\rfloor$ integers of the form $n^{\frac{1}{a}}$ between $1$ and $M$. So the percentage of integers of the form $n^{\frac{1}{a}}$ among the first $M$ integers is $$\frac{\lfloor{M^{\frac{1}{a}}}\rfloor}{M}\times 100\le \frac{M^{\frac{1}{a}}}{M}\times 100=\frac{100}{M^{1-\frac{1}{a}}}$$ which will be less than 1 for sufficiently large $M$.

But I am unable to prove the problem for any real $c$. I tried approximating reals with a sequence of rational numbers, but it didn't work well.

I was recently working on an open problem of similar kind, and I stumbled upon this sub-problem. How to solve this one(preferably not requiring too much heavy tool)? Thanks.

  • 2
    $\begingroup$ This was the problem A6 in 1971 Putnam. There is a solution here $\endgroup$ – Wojowu May 26 '19 at 16:47
  • 5
    $\begingroup$ @Wojowu Putnam problem was for 100 percents, not 1 percent. Although the proof may be modified. $\endgroup$ – Fedor Petrov May 26 '19 at 17:11
  • 1
    $\begingroup$ @FedorPetrov Ah, shame on me, I have actually not read the problem carefully enough! While the problem might still be of interest to the OP, I don't think the proof I link generalizes - it crucially depends on taking differences, and if we only know some fraction of terms are integers, we are not guaranteed any first difference is an integer! However, much more sophisticated tools, like ones discussed here, should give a proof. Of course, OP asks for an elementary proof, which I cannot really provide... $\endgroup$ – Wojowu May 26 '19 at 17:16
  • $\begingroup$ @Wojowu you may use other difference type operators $\endgroup$ – Fedor Petrov May 26 '19 at 17:22
  • 2
    $\begingroup$ The six exponential theorem would show that if $n_1$, $n_2$, $n_3$ are three integers with $n_i^c \in {\Bbb N}$ then $\log n_i$ are linearly dependent over ${\Bbb Q}$. (I assume that $c$ is irrational.) You should be able to show from this that at most $\ll (\log N)^2$ integers up to $N$ can satisfy $n^c \in {\Bbb N}$. $\endgroup$ – Lucia May 27 '19 at 1:20

We may modify the finite differences argument. Let $0=t_0<t_1<t_2<\ldots<t_d$ be fixed rational numbers. Our local goal is to find such rational coefficients $\lambda_0,\lambda_1,\ldots,\lambda_d$ that the mean value theorem $$\exists \tilde{x}\in [x,x+t_d]\colon\quad f^{(d)}(\tilde{x})=\sum \lambda_i f(x+t_i)$$ holds for any real $x$ and any $d$ times continuously differentiable on $[x,x+t_d]$ function $f$. This may be done as follows: consider the interpolating polynomial $$h(y)=\sum_{i=0}^d f(x+t_i)\prod_{j\ne i}\frac{y-x-t_j}{t_i-t_j}, \quad \deg h\leqslant d, \quad h(x+t_i)=f(x+t_i).$$ The function $g(y):=f(y)-h(y)$ has zeroes at $y=x+t_i,i=0,\ldots,d$. Therefore by Rolle's theorem there exists $\tilde{x}\in [x,x+t_d]$ such that $g^{(d)}(\tilde{x})=0$. This rewrites as $$ f^{(d)}(\tilde{x})=\sum \lambda_i f(x+t_i),\quad \lambda_i=\frac{d!}{\prod_{j\ne i} (t_i-t_j)}. $$

Now back to the problem. Choose a positive integer $d$ such that $c-d<0$ and integer $M>1000 d$. Call an integer $k$ nice if the set $[k\cdot M+1,k\cdot M+2,\ldots,k\cdot M+M-1]$ contains at least $d+1$ integers $y$ for which $y^c$ is integer. By density condition there exist arbitrarily large nice integers. Denoting the corresponding $d+1$ integers by $x+t_0,x+t_1,\ldots,x+t_d$, where $0=t_0<t_1<\ldots<t_d<M$, and applying our formula we get $$c(c-1)\ldots (c-d+1)\tilde{x}^{c-d}=\sum \lambda_i (x+t_i)^{c}\in (M!)^{-1}\mathbb{Z}.$$ But LHS becomes arbitrarily small while non-zero for large $x$.

| cite | improve this answer | |

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.