Is $\forall p,q,r \in \mathbb{N}$ Satisfiable?

[bomba923]

Quick question~

Is it true that

$$\forall p,q,r \in \mathbb{N} \text{ where } p > q > 0 ,$$
$$\exists \left\{ {a_0 ,a_1 ,a_2 , \ldots ,a_n } \right\} \subset \bigcup\limits_{i = 0}^{p - 1} {\left\{ {\frac{i}{q}} \right\}} {\text{ such that }}\frac{r}{q} = \sum\limits_{k = 0}^n { a_k \left( \frac{p}{q} \right) ^ k } \;\, ?$$

 

[bomba923]

Any ideas??

 

[bomba923]

Just an example,

Let $$p=3$$, $$q=2$$, and $$r=8$$.

Thus,
$$\bigcup\limits_{i = 0}^{p - 1} {\left\{ {\frac{i}{q}} \right\}} = \left\{ {0,\frac{1}{2},1} \right\}$$

Oh, and $$r/q = 8/2 = 4$$.

*Now, to satisfy the conditions
$$\left\{ {a_0 ,a_1 ,a_2 , \ldots ,a_n } \right\} \subset \bigcup\limits_{i = 0}^{p - 1} {\left\{ {\frac{i}{q}} \right\}}$$
and
$$\frac{r}{q} = \sum\limits_{k = 0}^n {a_k \left( {\frac{p}{q}} \right)^k }$$

-Let
$$\left\{ {a_0 ,a_1 ,a_2 , \ldots ,a_n } \right\} = \left\{ {1,\frac{1}{2},1} \right\}$$

And so,
$$\sum\limits_{k = 0}^n {a_k \left( {\frac{p}{q}} \right)^k} = 1\left( {\frac{3}{2}} \right)^0 + \frac{1}{2}\left( {\frac{3}{2}} \right) + 1\left( {\frac{3}{2}} \right)^2 = 4 = \frac{r}{q}$$

---------------------------
Again, I ask:

$$\forall p,q,r \in \mathbb{N} \text{ where } p > q > 0 , \; \text{does}$$
$$\exists \left\{ {a_0 ,a_1 ,a_2 , \ldots ,a_n } \right\} \subset \bigcup\limits_{i = 0}^{p - 1} {\left\{ {\frac{i}{q}} \right\}} {\text{ such that }} \,\frac{r}{q} = \sum\limits_{k = 0}^n { a_k \left( \frac{p}{q} \right) ^ k } \;\, ?$$

 

[Aditya89]

Excuse me, but how {1,1/2,1} is a subset of {0,1/2,1} in the above example?

 

[HallsofIvy]

Excuse me, but how {1,1/2,1} is a subset of {0,1/2,1} in the above example?

Because sets don't have "multiple" members. {1, 1/2, 1} is exactly the same as {1/2, 1} which is clearly a subset of {0, 1/2, 1}

 

[bomba923]

Hmm...to prove the original statement, we just have to show that:

$$\begin{gathered} \forall p,q \in \mathbb{N}\;{\text{where }}p > q > 0, \hfill \\ \mathbb{N} \subset \bigcup\limits_{k \geqslant 0} {\left\{ {\sum\limits_{n = 0}^\infty {\left( {\left\lfloor {\frac{k}{{p^n }}} \right\rfloor - p\left\lfloor {\frac{k}{{p^{n + 1} }}} \right\rfloor } \right)\left( {\frac{p}{q}} \right)^n } } \right\}} \hfill \\ \end{gathered}$$

 

[AKG]

Adopt the convention that 0 is a natural number. Let $\mathbb{Z}_p$ denote the set {0, 1, ..., p-1}. Given naturals r, p, and q such that p > q > 0, the problem can be considered as that of proving that there exists a natural n such that there exists a = (a₁, a₂, ...) in $A = \mathbb{Z}_p \times \mathbb{Z}_p \times \dots$ such that for all i > n, a_i = 0 and

$$r = \sum_{k=0}^{\infty}a_i\left(\frac{p}{q}\right)^k$$

Suppose there exists m such that r = (p^m+1)/q^m. Given an arbitrary element a of A, define deg(a) to be the least natural number such that a_k = 0 for all k > deg(a). I claim that given this configuration of r, p, and q (and I'll probably have to add in some extra hypotheses along the way) there exists no a in A satisfying the requirements.

Case 1: deg(a) > m
Case 2: deg(a) = m
Case 3: deg(a) < m

Case 1 implies that the sum that r is supposed to equal to is greater than or equal to (p/q)^m+1 which is greater than (p^m+1)/q^m which equals r, so the sum that is supposed to equal r is greater than r, so doesn't in fact equal r.

Case 2 implies that the sum is equal to:

$$\frac{p^m}{q^m} + \sum _{k=0} ^{m}a_k\left(\frac{p}{q}\right)^k$$

where a_m is in {0, 1, ..., p-2} and the rest of the a_k are in {0, 1, ..., p-1}. So we would get:

$$r = \frac{p^m}{q^m} + \sum _{k=0} ^{m}a_k\left(\frac{p}{q}\right)^k$$

$$\frac{1}{q^m} = \sum _{k=0} ^{m}a_k\left(\frac{p}{q}\right)^k$$

Hopefully you can see why this is impossible. If a_m > 0, then the right side is too big by virtue of p being greater than 1. If a_m = 0, then we get the right side being:

$$\sum _{k=0} ^{m-1}a_k\left(\frac{p}{q}\right)^k$$

But this means that you will be able to write the right side in the form z/q^m-1 where z is some natural number. So we would get:

$$\frac{1}{q^m} = \frac{z}{q^{m-1}}$$

$$1 = zq$$

Add the hypothesis that q > 1, and we get a contradiction.

Finally, in case 3, we get:

$$\frac{p^m + 1}{q^m} = \sum _{k=0} ^{deg(a)} a_k\left (\frac{p}{q}\right )^k$$

... I'm not sure where to go with this, or even if I'm proving/disproving the right thing. Keeping in mind the left-side has to be an integer, I don't see an easy way to make the above contradictory.

Note that if q = 1, then the whole problem is easy, and the answer is yes. It's just a consequence of the division algorithm, and we'd just be writing r in base p. If you consider the ring generated by (p/q) with the normal addition and multiplication, maybe there is generalized division algorithm that would give the desired result.

Initially, I tried proving that the answer to the question was yes. I tried using the idea of the division algorithm, but then I started thinking that I might have r's that were close to some power of p/q, but off by a small correction term, one that the terms in the sum on the right side couldn't take care of? That's where I got the idea for the r in my above attempt-of-a-proof. But now I'm not sure. The problem in my initial proof (in my attempt to prove the affirmative) is that I was doing what, in the terminology of the "proof" you see above, would amount to taking deg(a)=m, and we already see that won't work. This new proof shows that I would have to take deg(a) < m, and since I've had such a tough time showing that this leads to a contradiction, maybe rather than finding the highest power of (p/q) that divides a given r, and making that your n, I would have to check the specific r. If it is slightly larger than a power of (p/q), then maybe I should make my n one less than that highest power.

 

[bomba923]

-\Essentially, we just have to show whether

$$\forall p,q,r \in \mathbb{N}\;{\text{where }}p > q > 0,$$

$$\exists \left\{ {a_0,a_1,a_2,\ldots,a_n} \right\} \subset \mathbb{Z} \cap \left[ {0,p - 1} \right]$$

$$\text{such that }\,r = \sum\limits_{k = 0}^n {a_k \left( {\frac{p}{q}} \right)^k }$$

 

[Hurkyl]

$$\text{such that }\,r = \sum\limits_{k = 0}^n {a_k \left( {\frac{p}{q}} \right)^k }$$

How big can that sum be?

 

[AKG]

Some things to note:

If the problem has a solution where gcd(p,q) = 1, then it has a solution for any p, q.

Given gcd(p,q) = 1, two sums are equal iff the coefficients are equal, i.e.

$$\sum _{k=0}^na_k\left(\frac{p}{q}\right)^k = \sum _{k=0}^nb_k\left(\frac{p}{q}\right)^k \Leftrightarrow a_i = b_i$$

To prove this, we work by induction on n. When n = 0, this is obvious. Assume it holds for n = m. We want to show it holds for n = m+1. Well, we get:

$$\sum _{k=0}^{m+1}a_k\left(\frac{p}{q}\right)^k = \sum _{k=0}^{m+1}b_k\left(\frac{p}{q}\right)^k \Leftrightarrow a_i = b_i$$

$$\sum _{k=1}^{m+1}a_kp^kq^{m+1-k} = \sum _{k=1}^{m+1}b_kp^kq^{m+1-k}$$

$$(a_{m+1} - b_{m+1})p^{m+1} = \sum _{k=0} ^m(b_k - a_k)p^kq^{m+1-k}$$

$$p[p^m(a_{m+1} - b_{m+1})] = (b_0 - a_0)q^{m+1} + \sum _{k=1} ^m(b_k - a_k)p^kq^{m+1-k}$$

$$p[p^m(a_{m+1} - b_{m+1})] = (b_0 - a_0)q^{m+1} + p\sum _{k=1} ^m(b_k - a_k)p^{k-1}q^{m+1-k}$$

From this, we get that p | (b₀ - a₀), but since the b_i and a_i are less than p, this means that (b₀ - a₀) = 0, giving us that the 0^th coefficients are the same. Now since this is zero, we are left with:

$$p[p^m(a_{m+1} - b_{m+1})] = p\sum _{k=1} ^m(b_k - a_k)p^{k-1}q^{m+1-k}$$

$$p^m(a_{m+1} - b_{m+1}) = \sum _{k=1} ^m(b_k - a_k)p^{k-1}q^{m+1-k}$$

$$\sum _{k=0} ^ma_{k+1}p^kq^{m-k} = \sum _{k=0} ^ma_{k+1}p^kq^{m-k}$$

$$\sum _{k=0} ^m a_{k+1}\left(\frac{p}{q}\right)^k = \sum _{k=0} ^m b_{k+1}\left(\frac{p}{q}\right)^k$$

$$a_1 = b_1, \dots , a_{m+1} = b_{m+1}$$

the last line following from the inductive hypothesis.

We can also look at the problem as that of finding, given coprime p and q, and then given r, some natural n and some a_i in {0, 1, ..., p-1} such that

rqⁿ = a₀qⁿ + ... + a_kp^kq^n-k + ... + a_npⁿ

Now it's clear from this that q | a_n.

Also note that for all r, there is some M such that for all m > M, we get:

rq^m < p^m

So given an r, there are only so many values for n that could possibly work.

Now I'm not exactly sure how to formulate it, but I was thinking that we could use the pigeonhole principle in some way. We can note that if we have a sum going up to n, then the highest number we can make is:

$$\sum _{k=0}^n (p-1)p^kq^{n-k}$$

The number of multiples of qⁿ that are less than or equal to this number is

$$fl\left (\frac{(p-1)\sum_{k=0}^np^kq^{n-k}}{q^n}\right ) = fl\left ((p-1)\sum _{k=0}^n\left (\frac{p}{q}\right)^k\right)$$

where fl is the floor function. On the other hand, the number of distinct sums we can make that go up to n, where in particular q | a_n is:

$$fl\left (\frac{p}{q}\right )p^n$$

Well for now, this is just a collection of facts which maybe can be put together in some useful way, but I can't think of how to do so exactly right now.

 

[bomba923]

Using the sequence (and my TI-89)
$$A_n = \sum\limits_{k = 0}^n {\left( {\left\lfloor {\frac{n}{{p^k }}} \right\rfloor - p\left\lfloor {\frac{n}{{p^{k + 1} }}} \right\rfloor } \right)\left( {\frac{p}{q}} \right)^k }$$

I tried to derive the relationship between $n$ and $r$. In other words, calculate the value of $n$ given any $r = A_n$ (much like finding the inverse of a function or sequence...at least for the natural values of A_n).

As it turns out, A_n is not everywhere increasing, although an interesting & noticeable pattern is generated upon inspection. If someone can provide me with a download/link where I can plot sequences, I can attach the image here, of this sequence.

Now I'm not exactly sure how to formulate it, but I was thinking that we could use the pigeonhole principle in some way.

Not quite, though. There are sequences of $\left\{ {a_0 ,a_1 , \ldots ,a_n } \right\} \subset \mathbb{Z} \cap \left[ {0,p - 1} \right]$ for which
$$\sum\limits_{k = 0}^n {a_k \left( {\frac{p}{q}} \right)^k }$$
is not an integer.

You see, $\forall n \in \mathbb{N}$, there are
$$p^{n+1}$$
different sequences possible.

Of course,
For all sequences $\left\{ {a_0 ,a_1 , \ldots ,a_n } \right\}$ (that satisfy the conditions), the largest sum possible is
$$\left( {p - 1} \right)\sum\limits_{k = 0}^n {\left( {\frac{p} {q}} \right)^k }$$
which corresponds to a sequence where every term is $p-1$.
-And also, the largest possible integer--that $\left\{ {a_0 ,a_1 , \ldots ,a_n } \right\}$ can correspond to--is thus:
$$\left\lfloor {\left( {p - 1} \right)\sum\limits_{k = 0}^n {\left( {\frac{p} {q}} \right)^k } } \right\rfloor$$
---------------------------------------
However,
$$\forall q > 1, \; p^{n + 1} > 1 + {\left( {p - 1} \right)\sum\limits_{k = 0}^n {\left( {\frac{p}{q}} \right)^k } }$$

There will be a greater quantity of sequences possible (that satisfy the conditions) than is needed to express all the integers from zero to
$$\left\lfloor {\left( {p - 1} \right)\sum\limits_{k = 0}^n {\left( {\frac{p}{q}} \right)^k } } \right\rfloor$$

(Needless to say, the extraneous non-integer-representing sequences will represent non-integral rational numbers)

How big can that sum be?

Well, the sum can be any natural number. And as the
Frivolous Theorem of Arithmetic states ,

"Almost all natural numbers are very, very, very large."

 

[bomba923]

So,

$$\forall p,q,r \in \mathbb{N}{\text{ where }}p > q > 0,\;{\text{does}}$$

$$\exists \left\{ {a_0 ,a_1 , \ldots ,a_n } \right\} \subset \left\{ {0,1, \ldots ,p - 1} \right\}$$

$${\text{such that }}r = \sum\limits_{k = 0}^n {a_k \left( {\frac{p} {q}} \right)^k } \;?$$

?