2
$\begingroup$

Let's consider a set of numbers that one knows to high precision, and one knows or has a strong suspicion that `exact versions of these numbers' (see below) belong to a real extension of $\mathbb{Q}$. Is there an algorithm that allows one to find the rational coefficients? Even having a slow algorithm that is better than a brute force search would be interesting. Or is it known that this is not possible in general?

To be concrete, let us consider the extension $$ E = \mathbb{Q} (\cos(\pi/21), \cos(5\pi/21), \cos(11\pi/21), \cos(13\pi/21), \cos(17\pi/21), \cos(19\pi/21)) \ , $$ (note that $$\cos(\pi/21)+\cos(5\pi/21)+\cos(11\pi/21)+\cos(13\pi/21)+\cos(17\pi/21)+\cos(19\pi/21) = -\frac{1}{2} \ ,$$ so only six coefficients are required).

I know that the set of numbers I obtained numerically can be written in terms of the extension above. They are in fact the squares of $F$-symbols, satisfying the pentagon equations. By a brute-force search for coefficients with small denominators, one can identify some of the numbers. The ones found can then be used to find the others, by making use of the pentagon equations. However, for many of the numbers, both the numerators and denominators of the coefficients become large (up to 10^13 in the given example, so one needs the numbers to high precision to start with), and the procedure is very cumbersome. In more complicated situations, my brute force approach is not powerful enough, which is why I'm asking if a more sophisticated method/algorithm exists.

So more precisely, the question would be if there is an algorithm that finds an element $e \in E$, where $E$ is a real extension of $\mathbb{Q}$, such that $| e - r | < \epsilon$, for a given $r \in \mathbb{R}$ and precision $\epsilon$.

Improve this question
$\endgroup$
6
  • $\begingroup$ I guess I should have added that one should `make use of the extension', I'm not just asking for elements of $\mathbb{Q}$ that are close to some number $r\in\mathbb{R}$. I realise there is ambiguity in the question. $\endgroup$
    – eddy ardonne
    Commented Nov 25, 2021 at 11:41
  • 5
    $\begingroup$ This sounds like en.wikipedia.org/wiki/Integer_relation_algorithm : If you take $x_1,\ldots,x_{n-1}$ to be a $\mathbb{Q}$-basis of your field, and $x_n$ to be the real number in question, then a relation with small integer coefficients can be transformed to an expression of $x_n$ as a rational linear combination of your basis with small denominators and numerators in the coefficients. $\endgroup$
    – Achim Krause
    Commented Nov 25, 2021 at 12:47
  • $\begingroup$ @Achim: thanks for the interesting suggestion, one should be able to use it to find some of the numbers which have coefficients with small numerators/denominators. $\endgroup$
    – eddy ardonne
    Commented Nov 25, 2021 at 19:39
  • 1
    $\begingroup$ Do you know $E$ in advance? If so, then LLL does the job as Achim Krause explained. LLL even works when the numerators and denominators are not small. Typically, you can recognize with reasonable confidence whether LLL succeeds by looking the size of the coefficients. If it does not succeed then they will be really big (depending on the precision), in which case you can try to increase the precision. If you don't know $E$, apply LLL to $1,r,r^2,\ldots$ until it returns something interesting. $\endgroup$
    – François Brunault
    Commented Nov 26, 2021 at 19:54
  • $\begingroup$ @FrançoisBrunault Thanks for the clarification, I'll certainly try this out. Typically, I have a good idea about E, so that should work. $\endgroup$
    – eddy ardonne
    Commented Nov 27, 2021 at 10:42

0

Reset to default

You must log in to answer this question.