[math-fun] An early success of Rich's "number recognizer"
(= integer lattice reducer). I think I sent this long ago, but I just stumbled over the mail item, which I can never find when I'm looking for it.) In the late 70s, Robert Maas worked on adaptive data compression, and needed to solve these transcendental equations, In[597]:= FindRoot[{(1 - x)^(y - 2) x^(3 - 2 y) (1 - y)^(1 - y) y^y == 1, 1 == (1 - x)^(1 - x) x^x (1 - y) y^(x - 3)}, {x, 1`44/2}, {y, 1/2}, WorkingPrecision -> 44] for the coupled probabilities x and y: Out[597]= {x -> 0.64779887126104238549049829642576930694948772, y -> 0.54368901269207636157085597180174798652520330} We were curious whether they were algebraically independent, and fed their squares and crossterms into NUMREL, which Maas had implemented following an informal conversation with Rich. Here is a re-enactment with Mathematica's PSLQ. In[618]:= List @@ Expand[(1 + y + x)^2] Out[618]= {1, 2 x, x^2, 2 y, 2 x y, y^2} In[619]:= %.FindIntegerNullVector[% /. %597] Out[619]= 1 - 2 x y - y^2 Success! Is there any chance of a second relation? Try cubics: In[620]:= List @@ Expand[(1 + y + x)^3] Out[620]= {1, 3 x, 3 x^2, x^3, 3 y, 6 x y, 3 x^2 y, 3 y^2, 3 x y^2, y^3} In[621]:= %.FindIntegerNullVector[% /. %597] // Factor Out[621]= -3 y (-1 + 2 x - 2 x^2 + y) x and y are independently algebraic! Eliminating y, In[622]:= GroebnerBasis[{%/y, %%%}, {y, x}] // Factor Out[622]= {x (-1 + 2 x - 2 x^2 + 2 x^3), -1 + 2 x - 2 x^2 + y} So both satisfy cubics. In[625]:= Solve[0 == # & /@ (%622/{x, 1})][[1]] Out[625]= {x -> 1/3 (1 - (2 2^(2/3))/(13 + 3 Sqrt[33])^(1/3) + (13 + 3 Sqrt[33])^( 1/3)/2^(2/3)), y -> 1/18 (-6 + (32 2^(1/3))/(13 + 3 Sqrt[33])^(2/3) + ( 8 2^(2/3))/(13 + 3 Sqrt[33])^(1/3) - 2 (2 (13 + 3 Sqrt[33]))^(1/3) + (2 (13 + 3 Sqrt[33]))^(2/3))} In[627]:= N@% Out[627]= {x -> 0.6477988712610423, y -> 0.5436890126920761} as approximated earlier. --rwg
warning, I used FIXED font to type the message, Hello, about those 2 numbers, we have here 45 digits of precision, which I used, pari-GP own LLL routine can crack these numbers easily since 1990's here is what maple (with an interface to pari-gp) gives,
0.54368901269207636157085597180174798652520330; 0.54368901269207636157085597180174798652520330
gp([%],4); 4 3 2 2 x + x + x - 3 x + 1
factor(%); 3 2 (2 x - 1) (x + x + x - 1)
solve(%); 1/2 1/3 1/2 1/3 (17 + 3 33 ) 2 (17 + 3 33 ) 1/2, ----------------- - ------------------- - 1/3, - ----------------- 3 1/2 1/3 6 3 (17 + 3 33 )
1 + --------------------- - 1/3 1/2 (1/3) 3 (17 + 3 33 ) / 1/2 1/3 \ 1/2 1/3 1/2 |(17 + 3 33 ) 2 | (17 + 3 33 ) + 1/2 I 3 |----------------- + -------------------|, - ----------------- | 3 1/2 1/3| 6 \ 3 (17 + 3 33 ) / 1 + --------------------- - 1/3 1/2 (1/3) 3 (17 + 3 33 ) / 1/2 1/3 \ 1/2 |(17 + 3 33 ) 2 | - 1/2 I 3 |----------------- + -------------------| | 3 1/2 1/3| \ 3 (17 + 3 33 ) /
0.64779887126104238549049829642576930694948772; 0.64779887126104238549049829642576930694948772
gp([%],4); 4 3 2 6 x - 10 x + 10 x - 7 x + 2
factor(%); 3 2 (3 x - 2) (2 x - 2 x + 2 x - 1)
solve(%); 1/2 1/3 1/2 1/3 (26 + 6 33 ) 4 (26 + 6 33 ) 2/3, ----------------- - ------------------- + 1/3, - ----------------- 6 1/2 1/3 12 3 (26 + 6 33 )
2 + ------------------- + 1/3 1/2 1/3 3 (26 + 6 33 ) / 1/2 1/3 \ 1/2 1/3 1/2 |(26 + 6 33 ) 4 | (26 + 6 33 ) + 1/2 I 3 |----------------- + -------------------|, - ----------------- | 6 1/2 1/3| 12 \ 3 (26 + 6 33 ) / 2 + ------------------- + 1/3 1/2 1/3 3 (26 + 6 33 ) / 1/2 1/3 \ 1/2 |(26 + 6 33 ) 4 | - 1/2 I 3 |----------------- + -------------------| | 6 1/2 1/3| \ 3 (26 + 6 33 ) / They are indeed algebraic, with small coefficients. Best regards, Simon Plouffe
Most of the credit here goes to Maas, for turning my theoretical meanderings into working code. Many other people had similar ideas and actually wrote papers & created programs that accomplished more. Another small puzzle here: the expressions in [597] contain several terms with irrational algebraic exponents, and similar bases. So the individual terms are transcendental. But everything magically comes together to = 1. Amazing. Rich ----------- Quoting Bill Gosper <billgosper@gmail.com>:
(= integer lattice reducer). I think I sent this long ago, but I just stumbled over the mail item, which I can never find when I'm looking for it.)
In the late 70s, Robert Maas worked on adaptive data compression, and needed to solve these transcendental equations,
In[597]:= FindRoot[{(1 - x)^(y - 2) x^(3 - 2 y) (1 - y)^(1 - y) y^y == 1, 1 == (1 - x)^(1 - x) x^x (1 - y) y^(x - 3)}, {x, 1`44/2}, {y, 1/2}, WorkingPrecision -> 44]
for the coupled probabilities x and y:
Out[597]= {x -> 0.64779887126104238549049829642576930694948772, y -> 0.54368901269207636157085597180174798652520330}
We were curious whether they were algebraically independent, and fed their squares and crossterms into NUMREL, which Maas had implemented following an informal conversation with Rich. Here is a re-enactment with Mathematica's PSLQ.
In[618]:= List @@ Expand[(1 + y + x)^2]
Out[618]= {1, 2 x, x^2, 2 y, 2 x y, y^2}
In[619]:= %.FindIntegerNullVector[% /. %597]
Out[619]= 1 - 2 x y - y^2
Success! Is there any chance of a second relation? Try cubics:
In[620]:= List @@ Expand[(1 + y + x)^3]
Out[620]= {1, 3 x, 3 x^2, x^3, 3 y, 6 x y, 3 x^2 y, 3 y^2, 3 x y^2, y^3}
In[621]:= %.FindIntegerNullVector[% /. %597] // Factor
Out[621]= -3 y (-1 + 2 x - 2 x^2 + y)
x and y are independently algebraic! Eliminating y,
In[622]:= GroebnerBasis[{%/y, %%%}, {y, x}] // Factor
Out[622]= {x (-1 + 2 x - 2 x^2 + 2 x^3), -1 + 2 x - 2 x^2 + y}
So both satisfy cubics.
In[625]:= Solve[0 == # & /@ (%622/{x, 1})][[1]]
Out[625]= {x -> 1/3 (1 - (2 2^(2/3))/(13 + 3 Sqrt[33])^(1/3) + (13 + 3 Sqrt[33])^( 1/3)/2^(2/3)), y -> 1/18 (-6 + (32 2^(1/3))/(13 + 3 Sqrt[33])^(2/3) + ( 8 2^(2/3))/(13 + 3 Sqrt[33])^(1/3) - 2 (2 (13 + 3 Sqrt[33]))^(1/3) + (2 (13 + 3 Sqrt[33]))^(2/3))}
In[627]:= N@%
Out[627]= {x -> 0.6477988712610423, y -> 0.5436890126920761}
as approximated earlier. --rwg _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
Bill Gosper -
rcs＠xmission.com -
Simon Plouffe