True or False?

1. Apr 29, 2006

bomba923

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

2. Apr 29, 2006

matt grime

As stated that looks trivially false. I am assuming that your bracket is the legndre/jacobi symbol, and if so it is plus or minus 1 (or zero), the a_i are a *subset* (sets cannot have repeated elements) of {0,..p-1}, and as such just picking r large will do. The largest that sum could possibly be is 1+2+..+p-1 = (p-1)(p-2)/2

3. Apr 29, 2006

MathematicalPhysicist

i think it's true because it's limited to the existential quantifier, and thus we can find at least one sequence of a's which are subset to p-1's.

for example, p=2 q=1 n=2 r=a0+a1*2+a2*4, and thus r is natural, and you can find a combination where {a0,a1,a2} are subset of {0,1} like a0=a1=0 a2=1, etc.

4. Apr 29, 2006

matt grime

That is assuming that that symbol means the fraction p/q. As this was a number thoery thread I assumed differently.

In anycase, it is still false as stated, and you cannot have the set {a0,a1,a1} as a subset of {0,1} the former has 3 elements the latter has two elements. Sets cannot have repeated elements. {0,0,1} is not a set. But almost certainly that is being too picky.

Replace it with

$$a_i \in \{0,..,p-1\}$$

perhaps.

Last edited: Apr 29, 2006
5. Apr 29, 2006

MathematicalPhysicist

isn't the set {0,0,1} equivalent to {0,1}?

p.s
i know that repetition doesn't affect the set itself, but i didn't know it wasn't allowed.

6. Apr 29, 2006

matt grime

To be honest I forget these days, or rather I would avoid using such ambiguous notation as to avoid having to figure out what was meant. You could well be right.

7. Apr 29, 2006

Zurtex

The question doesn't make too much sense, it confuses sequences and sets, repetition of elements and the cardinality is somewhat ambiguous. But however you meant it I think this will apply:

Pretty trivial proof that it is true for r > 2, let p = q

$$r = \sum_{k=0}^n a_k$$

In other words, given an element of the natrual numbers can it be represented by a sum of smaller numbers, e.g 1 + 2 = 3, 1 + 3 = 4. All you have to do is prove that inductively, which is pretty trivial.

8. Apr 29, 2006

daveb

As Matt Grime pointed out, the way it's written, it isn't true (even if it is fractions). Let p=2, q=1, r=100. Then the coefficients a(i) are either 0, 1 or 2, and 100 = a(0) + a(1)*3/2 + a(2)*9/4 cannot be satisfied. It's written as for every p, q, and r.

9. Apr 29, 2006

bomba923

!Zurtex, in the original post, it clearly states "p > q > 0"

You CANNOT have p=q
----------------------------------
No!--it's just the fraction...p/q !

WHere did you get the 3/2 & 9/4 ?? If p=2 and q=1, you will have a0*(2/1) + a1*(4/1) + ... etc!

*Daveb, if p=2 and q=1, then p/q = 2
And in that case, any ai is either 0 or 1.

But...let's take your example, where p=2, q=1, and r=100.
The sequence {a0,a1,...,an} = {0,0,1,0,0,1,1}
as
0(1) + 0(2) + 1(4) + 0(8) + 0(16) + 1(32) + 1(64) = 100

Or, take the example where p=3, q=2, and r=100, in which case any ai is indeed 0,1, or 2. The sequence {a0,a1,...,an} = {1,0,2,1,0,0,2,1,2}
as
1(1) + 0 + 2(3/2)2 + 1(3/2)3 + 0 + 0 + 2(3/2)6 + 1(3/2)7 + 2(3/2)8 = 100

*Just one more example: let p=7, q=4, and r=23.
The sequence {a0,a1,...,an} = {2,5,4}
as
$$2 + 5\left( {\frac{7}{4}} \right) + 4\left( {\frac{7}{4}} \right)^2 = 23$$

Btw, q=1 and r ≤ p are just the trivially true cases.
No problem! I'll rewrite this less ambiguously:

$$\begin{gathered} \forall p,q,r \in \mathbb{N}\;{\text{where }}p > q > 0, \hfill \\ \exists \left\{ {a_0 ,a_1 , \ldots ,a_n } \right\}\;{\text{where }}\forall k \geqslant 0,\;a_k \in \left\{ {0,1, \ldots ,p - 1} \right\}, \hfill \\ {\text{such that }}r = \sum\limits_{k = 0}^n {a_k \left( {\frac{p} {q}} \right)^k } \hfill \\ \end{gathered}$$

Now, true or false?

Last edited: Apr 30, 2006
10. Apr 30, 2006

matt grime

Why do you insist on writing the a_i as a set?

$$\exists a_i, 0\leq i \leq n, a_i \in \{0,\ldots,p-1\}$$

11. Apr 30, 2006

bomba923

I don't. I intend to write it as a finite sequence of integers, each of which is between 0 (zero) and p-1 inclusively. Doesn't {a0,a1,...,an} denote a finite sequence?

*If not, how would you denote a finite sequence?

Last edited: Apr 30, 2006
12. Apr 30, 2006

Muzza

See the second line of his post?

13. Apr 30, 2006

matt grime

$$(a_i)_{i=0}^{i=n}$$

is how you more formally write sequences: round brackets with the limits marked top and bottom, though it is not usually necessary.

14. Apr 30, 2006

MathematicalPhysicist

shouldn't they be curled brackets {}?

15. Apr 30, 2006

matt grime

I wouldn't have thought so. Curly braces are reserved for sets, and sets are neither ordered, nor allow repetition, unlike sequences.

16. Apr 30, 2006

shmoe

$$\{a_i \}_{i=0}^{n}$$ is sometimes used to denote an ordered sequence, though not always. Sometimes <> are used. Sometimes () are used. There's no universal notation here.

17. Apr 30, 2006

Zurtex

Sorry, I mis-read that as p > 0 and q > 0.

Trivial Proof 2

n = 0
p > q > r > 0
a0=r

Think you can complete the rest.

18. Apr 30, 2006

daveb

That's what I meant to write...oops. As Matt pointed out, {...} is generally for sets, especially since you initially wrote it as one being a subset (rather than a sequnce) of the other. The way you rewrote it now makes more sense.

19. May 1, 2006

bomba923

Zurtex,
I never said r MUST be less than p!
Again, q=1 and r<p are just the trivially true cases!

What about q > 1 and r > p ?

Apparently not, but that's what I thought! :shy:
Alright, I'll rewrite the statement again (hopefully for the last time! unless other problems with semantics occur):

$$\begin{gathered} \forall p,q,r \in \mathbb{N}\,{\text{ where }} \, p > q > 0, \hfill \\ \exists \left( {a_k } \right)_{k = 0}^n \,{\text{ where }}\,\forall k \geqslant 0,\;a_k \in \left\{ {0,1, \ldots ,p - 1} \right\}, \hfill \\ {\text{such that }}r = \sum\limits_{k = 0}^n {a_k \left( {\frac{p} {q}} \right)^k } \hfill \\ \end{gathered}$$

~Now, true or false?

20. May 1, 2006

Zurtex

The question is still a little ill-posed, I'm not exactly sure what you want. Is the question:

Can you generate any natural number r for every pair (p,q)?

Edit: made a mistake, deleted it

Your question seemed to me to be, can you generate a pair (p,q) to satisfy any given natural number r. Which I can prove in several trivial cases, and I 've shown the other question to be false with a trivial counter example, so what do you want?!?
I never said you said that, however it is also trivially true in the case of:

q = anything
and
p > r

With a little more work that can be broadened a little to an easy proof (almost trivial) for:

q= anything
and
p > r or p = r

Hmm, I think I may of misunderstood you though, when you say: "q=1 and r<p" are you referring to 2 different cases? It really doesn't look like it, but it is also trivially true of the case of:

q = 1

Last edited: May 1, 2006