Representation of Rational Numbers by Formulas

[nworm]

Dear Experts.
Do you know some literature on
representation of rational numbers by formulas? TIA.

 

[arildno]

Eeh?

 

[nworm]

Realization of rational numbers by formulas.

For example, let B = {x + y, x - y, xy, x^(-1), 1},
B1 = {x + y, xy, x^(-1), 1}.
Constants 1 are formulas that realize number 1.
If F1, F2 are formulas in basis B (F1 realize number r1 and F2 realize number r2), and w from B is basic operation,
then F = w(F1,F2) is formula that realize number w(r1,r2) (by definition).
If operation w(x) = x^(-1) then w(F1) is formula, that realize number w(r1).

 

[AKG]

None of this makes sense to me.

 

[nworm]

For example, consider basis B = {x + y, x - y, xy, x^(-1), 1},
then
7/5 = (1 + 1 + 1 + 1 + 1 + 1 + 1)*(1 + 1 + 1 + 1 + 1)^(-1)
1/3 = (1 + 1 + 1)^(-1).

Did you see this formulas somewhere?

 

[arildno]

What nonsense is this?

 

[Hurkyl]

I think nworm is asking something about constructing rational numbers out of the constant 1 and the functions +, -, *, and [itex](\cdot)^{-1}[/itex]. As to what he's asking, and for what purpose, I have absolutely no clue.

By the way, nworm, depending on what you're asking, you have forgotten to specify we can use parentheses in expressions.

 

[nworm]

Yes, I am interested in constructing of rational numbers by formulas.
One day I read a book of arithmetical problems. I like the section that told about constructing of rational numbers by formulas (formulas are generated by superposition operations).
In this book "complexity of formula" is defined. It is number of symbols 1 in formula. "Complexity of number" r is minimal complexity of formula that realizes r.
(It is denoted as LB(r)).
Example of task:
Let B2 = {x + y, x^(-1), 1}, B3 = {x + y, (x^(-1)+y^(-1))^(-1), 1}.
Prove, that
LB3(r) = LB2(r), where r is any fraction.
I want to read about this else (exactly about rational numbers).

 

[AKG]

I see, so for example, you want to prove that, by using only the operations and functions in B2, the number of 1's required to make any fraction is the same as the number of 1's required to make that fraction, using only the things in B3 instead. I think you need to prove this, in some sense, by induction. Assume that you can create the numbers x and y using either B2 or B3 with the same number of 1's. Now, using B2, you can create x + y using no more 1's, and the same is true for B3. You can create x^-1 and y^-1 using no more 1's with B2, so can the same be said for B3? We'll get back to that. Using one more 1, you can create x+1, y+1, 1^-1, and 1 using B2, and the same is obviously true for B3. Using two more 1's, you can create 1+1 using B2, and the same is true for B3.

Using no more 1's with B3, you can create x+y and (x^-1 + y^-1)^-1 and using B2 you can obviously create x+y using no more 1's and you can create the second expression using no more one's as well (look at it for a second, it will become obvious). Using one more 1 with B3, you can create 1, x+1, y+1, (x^-1 + 1^-1)^-1, (1^-1 + y^-1)^-1, and if you think about it a little, you'll see that you can do these things with also just one more 1 using B2. Using two more 1's, you can create 1+1, and (1^-1 + 1^-1)^-1 = 1/2, and again, you'll see that this can easily be done with also using just two more 1's with B2.

So getting back to the one we missed? Can we invert numbers using B3 without using any more 1's? Actually, I don't think it can be done. Using x^-1 with B2 only requires you to have x occur once. The formulas that B3 has requires at least two things to appear, so it will require the 1's from two different things, and assuming one of those things is x, given that the other one will contain at least one 1, you have to use at least one more 1 to create x^-1. Now, this assumes that the best way to construct x^-1 is to create x, then invert it, and if what we're required to prove is indeed true, then this can't be the case for B3. Now clearly, the "quickest" (that is, the way using least 1's) way to create x^-1 with B2 is to create x and then invert it. Suppose it takes n 1's to create x, then it creates n 1's to create x^-1 if you create x and then invert it. If there is a quicker way to get directly to x^-1 that takes m < n 1's, then it only takes m 1's to create (x^-1)^-1 = x. We assumed n to be the least number of 1's required to make x, then assumed that there could be a quicker way to make x^-1, and found that this implies that there is some m < n such that you can create x with only m 1's, that is, there is a way quicker than the quickest, contradiction. So there is no quicker "direct" way to make x^-1, you have to just make x and then invert it. What we want to show, however, that this is not the case for B3. That there is some way to make x^-1 without making x first. We also want to show that the number of 1's required to make x (and hence the number of 1's required to make x^-1) using B2 is the same as the number of 1's required to make x^-1 using B3.

Actually, since the number of 1's required to make x is the same as the 1's required to make x^-1 using B2, the above is equivalent to asking that we prove that it takes the same amount of 1's to create x^-1 with B2 as it does for B3, and since x is arbitrary, we may as well say that it takes the same number of 1's to create x using B2 or B3. This is actually what we wanted to prove in the first place, so we're back at the beginning. Note that now, however, we're not assuming anything specific about x (we've left the scope of the assumption that B2 and B3 realize x with the same number of 1's).

Maybe we can go back to assuming that x takes the same 1's with B2 or B3, and still prove that x^-1 takes the same 1's using B3. Note that for B2 to make x, it had to have added two previous numbers w and z. Let's assume that B3 can make w and z with as many 1's as B2 (this is consistent with our assumption because it then takes B3 no more 1's to add w and z together, just as B2 would do, however, this doesn't follow from our assumption, it's an additional one). Can we use B3 to take w and z and jump straight to x^-1 without using any more 1's? Actually, I don't see this working, but I've thrown some ideas out, maybe someone can build on them (note that using B3's second operation, you just get zw/(z + w), but we need 1/(z + w)).

 

[nworm]

Thank you very much These ideas are very interesting
I am thinking that we can't create x^-1 by using B3.
I have found the solution of this task (on the other page)

As function (x^-1 + y^-1)^-1 is expressed in B2 as noniterated superposition, then any formula in B3 can be transformed to formula in B2 without changing of complexity. This implies that LB3(r) >= LB2(r).
If a corollary formula of a formula in B2 is given by F^-1, then this corollary formula is represented as (F1^-1+F2^-1+...+Fn^-1)^-1, where Fi are corollary formulas of less complexity or constants 1. Write a new formula G.

G=((...((F1^-1+F2^-1)^-1)^-1+F3^-1)^-1)^-1+...+Fn^-1)^-1 = g(g(...g(g(F1,F2),F3)...),Fn), where g(x,y)=(x^-1+y^-1)^-1.

The formula F and G are equivalent. The complexity of G is the same as the complexity of F. By iterating this transformation we can find a formula H in B3. The complexity of H is the same as the complexity of F. Therefore LB3(r) <= LB2(r). Therefore LB3(r) = LB2(r).

I am repeating my question. Do you know some literature about this (about rational numbers)
I didn’t read a lot of books in the field of number theory (I read “A Course in Number Theory and Cryptography” by Neal Koblitz only).

 

[AKG]

Thank you very much These ideas are very interesting
I am thinking that we can't create x^-1 by using B3.

x^-1 introduces no new complexity in B3. Starting with a number and then inverting it in B3 will introduce new complexity. However, maybe there's someway to start with a number y that requires less complexity than it takes to realize x itself, and then do some things to y that end up with x^-1, the end result requiring the same complexity as B2. So B3 gives x^-1, but does so in a roundabout way that ends up taking the same complexity. However, you were asked to prove that LB2(r) = LB3(r) for any r. So why would you say that we can't create x^-1?

As function (x^-1 + y^-1)^-1 is expressed in B2 as noniterated superposition, then any formula in B3 can be transformed to formula in B2 without changing of complexity. This implies that LB3(r) >= LB2(r).

Yes, that's correct.

If a corollary formula of a formula in B2 is given by F^-1, then this corollary formula is represented as (F1^-1+F2^-1+...+Fn^-1)^-1, where Fi are corollary formulas of less complexity or constants 1. Write a new formula G.

G=((...((F1^-1+F2^-1)^-1)^-1+F3^-1)^-1)^-1+...+Fn^-1)^-1 = g(g(...g(g(F1,F2),F3)...),Fn), where g(x,y)=(x^-1+y^-1)^-1.

The formula F and G are equivalent. The complexity of G is the same as the complexity of F. By iterating this transformation we can find a formula H in B3. The complexity of H is the same as the complexity of F. Therefore LB3(r) <= LB2(r). Therefore LB3(r) = LB2(r).

I see, very nice. So we are using induction. G (in B3) has the same complexity as F (in B2) as long as the corollary formulas can be made in B3 with the same complexity. But they can since each corollary formula F_i is again just in the form (F_i1^-1 + ... + F_in^-1)^-1 where formulas F_ij are corollary to F_i, and hence have even smaller complexity. So using the exact same method, G_i can be made with the same complexity assuming each G_ij can be made, and we subsequently look at corollaries of smaller and smaller complexity, until we inevitably reach our base case for our induction. In this case, we're using strong induction.

I am repeating my question. Do you know some literature about this (about rational numbers)
I didn’t read a lot of books in the field of number theory (I read “A Course in Number Theory and Cryptography” by Neal Koblitz only).

Sorry, I've never seen anything like this.