mathematical challenge, number theory, A005245, integer complexity, complexity theory, exponentiation, mathematics is inconsistent, arithmetic is inconsistent, inconsistency
Any comments are welcome: Karlis.Podnieks@lu.lv
Mathematical Challenge
By Karlis Podnieks
University of Latvia
Number Theory Consider representing of natural numbers by using 1, +, * and brackets. One can prove easily that the best way of representing the powers of 3 is as follows: 3n = (1+1+1)*(1+1+1)*...*(1+1+1). All the other variants contain more than 3n 1's. Problem 1. Is 2n = (1+1)*(1+1)*...*(1+1) the best way of representing the powers of 2? It is the best way at least for n≤39 – as verified by Janis Iraids. More about the context – see A005245 in the The On-Line Encyclopedia of Integer Sequences. February 26, 2011 Added later: H. Altman, J. Zelinsky. Numbers with Integer Complexity Close to the Lower Bound, INTEGERS, Vol. 12A, 2012 (available online). J. Iraids, K. Balodis, J. Čerņenoks, M. Opmanis, R. Opmanis, K. Podnieks. Integer Complexity: Experimental and Analytical Results. Scientific Papers University of Latvia, Computer Science and Information Technologies, Vol. 787, 2012, pp. 153-179 (available online). |
Complexity Theory Consider representing of natural numbers by using 1, +, *, ^ and brackets (^ stands for exponentiation), for example: 10^(10^(10^10)). One cannot compute the “value” of this short expression in real time (whatever that means). Problem 2. How complicated is comparing the values of two expressions based on {1, +, *, ^}, the longer expression having the length n? More about the
context – see: February 26, 2011 |
Mathematical Logic Problem 3. Prove that any formal theory of natural numbers allows deriving of contradictions – as predicted in 1908 by Henri Poincare. According to Gödel's First Incompleteness Theorem, any formal theory of natural numbers is either inconsistent, or incomplete. The final step: prove that the second clause can be dropped. More about the context – see the end of Section 6.1 of my book about Goedel's Theorem. Possibly, the first real step towards a solution is announced in: N. V. Belyakin. One $omega$-inconsistent formalization of set theory. The 9th Asian Logic Conference, 16-19 August, 2005, Novosibirsk, Russia (online abstract),
where the following is announced: "From this fact follows, in particular, that the existence of strongly inaccessible cardinals is refutable in ZF."
Note. The English translation of the abstract contains an error: one should remove [in] from the statement “It is not hard to check that T is [in]consistent wrt ZF+(existence of strongly inaccessible cardinals)”. February 26, 2011 |
mathematical challenge, number theory, A005245, integer complexity, complexity theory, exponentiation, mathematics is inconsistent, arithmetic is inconsistent, inconsistency