Monic polynomial from absolute value information 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.)
 A: 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.
