- #1
nworm
- 31
- 0
Dear Experts.
Do you know some literature on
representation of rational numbers by formulas? TIA.
Do you know some literature on
representation of rational numbers by formulas? TIA.
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}?nworm said:Thank you very much :rofl: These ideas are very interesting :tongue2:
I am thinking that we can't create x^{-1} by using B3.
Yes, that's correct.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).
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.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).
Sorry, I've never seen anything like this.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).