For vector basis $b\_1,..,b\_n$ on a finite extension $F$ of $\mathbb{Q}$, where $-1$ is not a sum of squares, each linear order on $F$ is determined by an order on the basis. This uses information about where the $b\_i$ sit among the rationals, and that information can be gained from Sturm's algorithm applied to any polynomial defining the field. 


Is there a good reference for defining/computing orderings on formally real number fields?



Definability of orderings on a formally real number field
(Originally a comment, reposted as an answer:)


Choose a primitive element $\alpha$ of F (i.e. such that $F=\mathbf{Q}(\alpha)$). Let $f$ be its minimal polynomial. Then the data of a field ordering of $F$ is equivalent to the data of an interval in $\mathbf{Q}$ which contains a unique root of $f$. Given any such interval, it's easy to refine it to an arbitrarily small one, algorithmically, just by repeated bisection.


Hence, given such an interval, and any $x \in F$ (expressed as a polynomial in $\alpha$ of degree $< [F : \mathbf{Q}]$), we can easily compute an arbitrarily small rational interval containing the image of $x$, and thus determine whether $x>0$ or not. This is actually how some computer algebra systems, e.g. Sage, compute with algebraic real numbers.


I don't see any nice way of bounding *a priori* the running time of this algorithm in terms of the basis coefficients of $x$, unfortunately.


