Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Representation of Rational Numbers by Formulas

  1. Aug 24, 2005 #1
    Dear Experts.
    Do you know some literature on
    representation of rational numbers by formulas? TIA.
     
  2. jcsd
  3. Aug 24, 2005 #2

    arildno

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

  4. Aug 24, 2005 #3
    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).
     
  5. Aug 24, 2005 #4

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    None of this makes sense to me.
     
  6. Aug 25, 2005 #5
    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?
     
  7. Aug 25, 2005 #6

    arildno

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    What nonsense is this???
     
  8. Aug 25, 2005 #7

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
    Last edited: Aug 25, 2005
  9. Aug 25, 2005 #8
    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).
     
  10. Aug 25, 2005 #9

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    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)).
     
  11. Aug 26, 2005 #10
    Thank you very much :rofl: These ideas are very interesting :tongue2:
    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) :biggrin:

    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) :confused:
    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).
     
  12. Aug 26, 2005 #11

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    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?
    Yes, that's correct.
    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 Fi is again just in the form (Fi1-1 + ... + Fin-1)-1 where formulas Fij are corollary to Fi, and hence have even smaller complexity. So using the exact same method, Gi can be made with the same complexity assuming each Gij 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.
    Sorry, I've never seen anything like this.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Representation of Rational Numbers by Formulas
  1. Rational Numbers (Replies: 2)

Loading...