# 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