{"id":5341,"date":"2020-01-09T05:30:49","date_gmt":"2020-01-09T03:30:49","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=5341"},"modified":"2020-01-16T08:47:21","modified_gmt":"2020-01-16T06:47:21","slug":"teorema-de-hilbert-waring","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/teorema-de-hilbert-waring\/","title":{"rendered":"Teorema de Hilbert-Waring"},"content":{"rendered":"<p>El <a href=\"http:\/\/bit.ly\/369KkkD\">problema de Waring<\/a>, propuesto por Edward Waring consiste en d\u00e9terminar si, para cada n\u00famero entero k mayor que 1, existe un n\u00famero n tal que todo entero positivo se puede escribir como una suma de k-potencias de n\u00fameros positivos con n sumandos como m\u00e1ximo.<\/p>\n<p>La respuesta afirmativa al problema, aportada por David Hilbert, se conoce como el teorema de Hilbert-Waring. Su enunciado es<\/p>\n<blockquote><p>\nPara cada n\u00famero entero k, con k \u2265 2, existe un entero positivo g(k) tal que todo entero positivo se puede expresar como una suma de a lo m\u00e1s g(k) k-\u00e9simas potencias.\n<\/p><\/blockquote>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   descomposiciones :: Integer -> Integer -> Integer -> [[Integer]]\n   orden :: Integer -> Integer -> Integer\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(descomposiciones x k n) es la lista de descomposiciones de x como suma de n potencias con exponente k de n\u00fameros enteros positivos.<\/li>\n<\/ul>\n<pre lang=\"text\">  \n     descomposiciones 9   2 1  ==  [[9]]\n     descomposiciones 9   3 1  ==  []\n     descomposiciones 9   3 2  ==  [[1,8]]\n     descomposiciones 9   4 9  ==  [[1,1,1,1,1,1,1,1,1]]\n     descomposiciones 25  2 2  ==  [[9,16]]\n     descomposiciones 133 2 3  ==  [[8,125]]\n     descomposiciones 38  3 2  ==  [[1,1,36],[4,9,25]]\n<\/pre>\n<ul>\n<li>(orden x k) es el menor n\u00famero de sumandos necesario para expresar x como suma de k-\u00e9simas potencias. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">  \n     orden 9  2  ==  1\n     orden 9  3  ==  2\n     orden 9  4  ==  9\n     orden 10 2  ==  2\n     orden 10 3  ==  3\n     orden 10 4  ==  10\n     [maximum [orden x k | x <- [1..1000]] | k <- [1..6]] == [1,4,9,19,37,73]\n<\/pre>\n<p>Comprobar el teorema de Hilbert-Waring para k hasta 7; es decir, para todo n\u00famero x positivo se verifica que<\/p>\n<pre lang=\"text\">\n   orden x 2 <= 4   \n   orden x 3 <= 9   \n   orden x 4 <= 19  \n   orden x 5 <= 37  \n   orden x 6 <= 73  \n   orden x 7 <= 143\n<\/pre>\n<p>y, en general,<\/p>\n<pre lang=\"text\">\n   orden x k <= 2^k + floor ((3\/2)^k) - 2\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Test.QuickCheck\n\ndescomposiciones :: Integer -> Integer -> Integer -> [[Integer]]\ndescomposiciones x k n =\n  sumas x (takeWhile (<= x) (potencias k)) n\n\n-- (potencias n) es la lista de las potencias de n\n--    take 7 (potencias 2)  ==  [1,4,9,16,25,36,49]\n--    take 7 (potencias 3)  ==  [1,8,27,64,125,216,343]\npotencias :: Integer -> [Integer]\npotencias n = map (^n) [1..]\n\n-- (sumas n ys x) es la lista de las descomposiciones de x como\n-- sumas de n sumandos de la lista creciente ys. Por ejemplo,\n--    sumas 3 [1,2] 2  ==  [[1,2]]\n--    sumas 4 [1,2] 2  ==  [[2,2]]\n--    sumas 5 [1,2] 2  ==  []\n--    sumas 5 [1,2] 3  ==  [[1,2,2]]\n--    sumas 6 [1,2] 3  ==  [[2,2,2]]\n--    sumas 6 [1,2,5] 2  ==  [[1,5]]\nsumas :: Integer -> [Integer] -> Integer -> [[Integer]]\nsumas _ [] _                   = []\nsumas x ys 1     | x `elem` ys = [[x]]\n                 | otherwise   = []\nsumas x (y:ys) n | y > x       = []\n                 | otherwise   = map (y:) (sumas (x-y) (y:ys) (n-1)) ++\n                                 sumas x ys n\n\norden :: Integer -> Integer -> Integer\norden x k = head [n | n <- [1..]\n                    , not (null (descomposiciones x k n))]\n\n-- El teorema es                                 \nteorema_Hilbert_Waring :: Integer -> Integer -> Property\nteorema_Hilbert_Waring x k =\n  x > 0 && k >= 2\n  ==>\n  orden x 2 <= 4   &#038;&#038;\n  orden x 3 <= 9   &#038;&#038;\n  orden x 4 <= 19  &#038;&#038;\n  orden x 5 <= 37  &#038;&#038;\n  orden x 6 <= 73  &#038;&#038;\n  orden x 7 <= 143 &#038;&#038;\n  orden x k <= 2^k + floor ((3\/2)^k) - 2\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck teorema_Hilbert_Waring\n--    +++ OK, passed 100 tests.\n<\/pre>\n<h4>Referencia<\/h4>\n<ul>\n<li>Basado en <a href=\"http:\/\/bit.ly\/2MFCbg5\">Hilbert-Waring theorem<\/a> de ProofWiki.<\/li>\n<\/ul>\n<h4>Pensamiento<\/h4>\n<blockquote><p>\n\u00a1Y en la tersa arena,<br \/>\ncerca de la mar,<br \/>\ntu carne rosa y morena,<br \/>\ns\u00fabitamente Guiomar!<\/p>\n<p>Antonio Machado\n<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"<p>El problema de Waring, propuesto por Edward Waring consiste en d\u00e9terminar si, para cada n\u00famero entero k mayor que 1, existe un n\u00famero n tal que todo entero positivo se puede escribir como una suma de k-potencias de n\u00fameros positivos con n sumandos como m\u00e1ximo. La respuesta afirmativa al problema, aportada por David Hilbert, se&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[7],"tags":[8,26,71,10,181,141,11,6,34,146],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5341"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=5341"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5341\/revisions"}],"predecessor-version":[{"id":5404,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5341\/revisions\/5404"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=5341"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=5341"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=5341"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}