Re: ranges of integer polynomials

On Wed, 10 Oct 2007 20:44:11 -0700, adler.math@xxxxxxxxx wrote:

On Oct 10, 7:19 pm, quasi <qu...@xxxxxxxx> wrote:

On Wed, 10 Oct 2007 11:24:07 -0700, adler.m...@xxxxxxxxx wrote:

On the complement (in N, not Z) of the k-th powers for fixed k>1, a
variant of Galathaea's procedure will work. ..........

Can you sketch the idea?

Here it is. The same idea can be used to show that if R is a
polynomial in one variable, with positive integer coefficients,
and R(0)=0, then the complement (in N) of the range of R, as the
variables range over non-negative integers, is itself the range of a
polynomial. I expect the technique can be extended further. For
example, one can show that the set of positive integers which are
neither a square nor a cube is the range of a polynomial. Below is a
proof of the fact that the complement in N of the set of perfect k-th
powers is the range of a polynomial. The basic idea is due to
Galathaea. However, she sent the "exceptions" to the negative
integers, while this argument sends them to numbers that are not
perfect k-th powers, making them fully unexceptional.

Forgive the LaTeX. I really find it hard NOT to use it, the typing
fingers automatically put in the $ signs, and other bits of LaTeX
code.

Please try _not_ to.

The standard in sci.math is to try hard to make the posts readable for
the general reader. In particular, knowledge of latex is not assumed.
For many readers, perhaps most, the many $ signs slow down the process
of comprehension. Of course, the $ signs can be easily edited out, but
_you_ should do that, not each individual reader. Similarly for all
the \begin and \end directives.

-------------------------------------
A Polynomial whose Range is the Positive Integers which are not
Perfect $k$-th Powers

Let $k$ be an integer greater than 1. We show that there is a
polynomial $P$ whose range consits of all positive integers which are
not a perfect $k$-th power.

It is convenient to have all variables range over the non-negative
integers. If it is desired to make the variables range over all the
integers, just replace any variable $v$ by
$v_1^2+v_2^2+v_3^2+v_4^2$.

Let $P(x,u,v)$ be the polynomial given by the formula
\[
P(y,x, u,v)=(y-x^k-u-1)^2 +((x+1)^k -y-v-1)^2.
\]

\begin{lemma}
For any given $y$, there exist $x$, $u$, $v$ such that $P(y,x,u,v)=0$
if and only if $y$ lies strictly between two consecutive $k$-th
powers.
\end{lemma}

\begin{proof}
Suppose that $y$ lies strictly between $x^k$ and $(x+1)^k$. Then in
particular $y-x^k >0$. If we let $u=y-x^k -1$, then $y-x^k-u-1=0$.
Similarly, if we let $v=(x+1)^k-y-1$, then $(x+1)^k -y-v-1=0$, and it
follows that for these values of $y$, $x$, $u$, and $v$, we have
$P(y,x,u,v)=0$.

Conversely, suppose that there for particular $x$, $u$, and $v$ we
have $P(y,x,u,v)=0$. Then $y=x^k+u+1$, which implies that $y>x^k$,
and $(x+1)^k=y+v+1$, which implies that $y<(x+1)^k$.
\end{proof}

Define the polynomial $Q(z, x,u,v)$ by the formula
\[
Q(z,x,u,v)= (z+1)^kP^k(z+1,x,u,v) +(z+1).
\]
We show that the range of $Q$ consists of all the positive integers
that are not $k$-th powers.

Take any positive integer which is not a perfect $k$-th power. This
integer can be represented as $z+1$ for suitable non-negative $z$.
Since $z+1$ is not a perfect $k$-th power, there exist $x$, $u$, $v$
such that $P(z+1, x,u,v)=0$. For these values of $z$, $x$, $u$, $v$,
we have $Q(z,x,u,v)=z+1$. Thus $z+1$ is in the range of $Q$.

Next we show that nothing in the range of $Q$ can be a perfect $k$-th
power. Suppose that $z+1$ is not a $k$-th power. Then for all (non-
negative integer) values of $x$, $u$, and $v$, we have $P(z+1,x,u,v)
\ge 1$. For simplicity, let $b= P(z+1,x,u,v)$. Then $Q(z,x,u,v)=(b(z
+1))^k + (z+1)$.
However, the next perfect $k$-th power after $(b(z+1))^k$ is larger
than
$(b(z+1))^k +(z+1)$, and therefore $Q(z,x,u,v)$ cannot be a perfect $k
$-th power.

Yes, it works well, very nice.

quasi
.

Relevant Pages

  • REPOST: Re: Pomerance/Crandall "Prime Numbers" book: inequality question
    ... >which I already own (I bought it a few years ago and only read a few ... >Why is this inequality true? ... one of those powers of p for each prime p <= x and multiplying them ... This gives us Pdistinct positive integers, ...
    (sci.crypt)
  • Re: Pomerance/Crandall "Prime Numbers" book: inequality question
    ... >out, and before I buy it I figured I should read the first edition, ... >which I already own (I bought it a few years ago and only read a few ... one of those powers of p for each prime p <= x and multiplying them ... This gives us Pdistinct positive integers, ...
    (sci.crypt)
  • Re: ranges of integer polynomials
    ... Can rangebe the set of all positive integer non-cubes? ... For which positive integers k>2, if any, can the set of all ... positive integer non-k'th powers be realized as range? ...
    (sci.math)
  • Re: ranges of integer polynomials
    ... Can rangebe the set of all positive integer non-cubes? ... For which positive integers k>2, if any, can the set of all ... positive integer non-k'th powers be realized as range? ...
    (sci.math)