Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.)

share|improve this question
    
Can you pick the $x_i$? –  Daniel Litt Jul 27 '10 at 20:20
    
If you can pick the x_i, then you can choose x_i = i and use finite differences to work out what choice of signs makes the (d+1)th finite difference zero and the dth finite difference d!. (And then, of course, you can use your finite difference table to write the polynomial in the Newton basis.) –  Qiaochu Yuan Jul 27 '10 at 20:25
    
No. The $x_i$ are fixed; intrinsic to the underlying structure of the moduli space. –  Aeryk Jul 27 '10 at 20:26
2  
The conditions you give need not uniquely determine the polynomial. For example, evaluate the polynomials $X^2-2$, $X^2-2X+2$ and $X^2-4X+2$ at $\{0,1,2\}$. You will run in to this same problem whenever you try to find a quadratic with $f(x_i)=\pm(x_i-x_j)(x_i-x_k)$ - there are 3 monic polynomials satisfying this permuted by $S_3$. –  Tony Scholl Jul 27 '10 at 22:44
1  
There's a solution to this using lattice reduction for which I'm working out the details. The idea is that you first write the idempotents in the algebra $\mathbb{Q}[X]/<(x-a_1) \cdots (x-a_d)>$ as vectors and add more coordinates for each to keep the coefficients under control. –  Victor Miller Jul 28 '10 at 15:42

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
After thinking about it some more I realized that this problem is really "subset sum" in disguise. We're interested in solutions of $\sum_i \epsilon_i c_i = 1$ where $\epsilon_i = \pm 1$. Let $\delta_i = (1+\epsilon_i)/2$ and $C=\sum_i c_i$. Then the problem is equivalent to $\sum_i \delta_i c_i = (1+C)/2$ with $\delta_i =0,1$ which is exactly the NP-complete problem subset sum. But depending on the information from the sizes of the $c_i$ it might be easy -- see the Odlyzko paper I referred to. I suspect that the $c_i$ arising in the context of the motivation aren't random. –  Victor Miller Jul 30 '10 at 11:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.