I'm trying to find the minimal (monic) polynomial $M(x)$ (over the rationals) for an algebraic number. I know the degree of the polynomial (call it $d$) and I have $d+1$ data points of the form $(x\_i, |M(x\_i)|)$. The $x\_i$ are all rational numbers, so the $|\cdot|$ is just regular absolute value.


If it wasn't for the absolute value sign, it'd be a straight-forward polynomial fit. However, to only way I've been able to solve for $M(x)$ is fitting a polynomial for each of the $2^d$ choices of plus/minus on the second coordinate, and then finding one that's monic.


Luckily, so far this has always produced one and only one such polynomial. Anybody know a more feasible/elegant way to do this?


(For more motivation than you actually care for, see <http://course1.winona.edu/eerrthum/Papers/MAANCS081018.pdf> where on slide 8 (page 34) I mention the brute force method.The last slide contains an example calculation.)


(Feel free to re-tag as appropriate.)



Monic polynomial from absolute value information
Here's a solution using lattice reduction:


1) Find degree $d$ polynomials $p\_i(x)$ such that $p\_i(x\_j) = |M(x\_i)| \delta\_{i j}$.


2) Let $c\_i$ be the coefficient of $x^d$ in $p\_i(x)$, and $c$ the $d+1$ long column vector whose coordinates are $c\_i$.


3) Find a matrix $U \in SL\_{d+1}(\mathbb{Z})$ such that $U c = e$, where $e$ is the $d+1$ long column vector with a 1 in the first coordinate and zeros elsewhere. Added later:


not quite. Let $D$ be a common denominator of all the elements of $c$, and form a $d+1 \times d+1$ matrix, $A$, whose first column is $cD$ and the lower $d \times d$ block is the identity matrix (with the rest of the top row 0). Find the Hermite normal form: $U \in SL\_{d+1}(\mathbb{Z})$, $U A = H$. The first column of $H$ will be zeros below the first entry, which will be a positive integer $r$. In order for there to be a solution it is necessary that $r | D$. Form a new matrix $U'$ by multiplying the top row of $U$ by $D/r$.


4) The answer (see below) is a vector in the $\mathbb{Z}$-lattice generated by the bottom $d$ rows of $U'$ which is close to the top row.


Namely, form the matrix $W$ by adjoining a $d+1 \times d+1$ identity matrix to the right of $c$. Since only the coefficient of $x^d$ matters in the answer, we can see that an answer will be given by some integer linear combination of the rows of $W$ which has $\pm 1$ in the last $d$ coordinates. The squared Euclidean length of that vector will be $d+1$, which is quite short. There are a number of algorithms for finding a closest vector (in theory for general lattices it's a hard problem, but in practice in a lattice like this it's not too hard). For a nice account of how to do it look in <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.81.8089> starting around page 14.


The idea here is to prepend a column to $U'$ which is a unit vector with 1 in the first position and 0's everywhere else. Now multiply the rest of the matrix (all columns but the first) by a large scaling factor, $s$. This will make sure that the first row will show up in the linear combination forming the shortest basis vector.


Lattice reduction will supply a short vector in the lattice which we know that our answer is. We then read off the coefficients of the $p\_i$ in the last $d+1$ coordinates.


I've programmed this, and tested it on random polynomials of degree 20, and it successfully finds the $\pm 1$ combination leading to a monic polynomial.


In Tony Scholl's example of three different polynomials having the same data, the lattice generated has a lot of short vectors, so in that case one needs to enumerate short vectors to pick out the answers.


