Timeline for Algorithm for checking linear independence of algebraic numbers
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 6, 2023 at 22:07 | history | edited | YCor | CC BY-SA 4.0 |
formatting, added tag
|
| Mar 6, 2023 at 20:54 | answer | added | toghrul | timeline score: 1 | |
| Jun 6, 2018 at 5:46 | comment | added | Jose Capco | It's the determinant of the matrix induced by the trace-form. If you already got the reference (Cohen), it is in Proposition 4.4.1 of 3rd edition. | |
| May 31, 2018 at 16:50 | answer | added | Alex Kindel | timeline score: 1 | |
| May 30, 2016 at 20:34 | comment | added | Pranjal Dutta | Okay, thanks. There is an another related question which I could not find (most probably related to this one). Suppose you are given $n$ algebraic numbers $a_i$ , how to check whether $\sum \alpha_i = 0$ ? See using linear independence you can give a NP algorithm (find the maximal independent set and then guess the coefficients of others while writing in terms of the maximal elements and then check whether all coefficients are indeed 0 or not) . But I guess there is a similar Polytime algorithm for this also but could not find anything. Can we give a polytime algo for this also? | |
| May 28, 2016 at 22:34 | comment | added | WhatsUp | They are efficient enough at least for a small number of inputs. The key point you need is probably the factorization of a polynomial over $\mathbb{Q}$, for which some efficient algorithm involving LLL exist. | |
| May 28, 2016 at 21:20 | comment | added | Pranjal Dutta | Which determinant? Can you elaborate? are you aware that they are efficient or not? I will look at the book . I think there is some algorithm using LLL . But I am not sure. | |
| May 28, 2016 at 21:08 | comment | added | WhatsUp | With some search I found GTM 138: A Course in Computational Algebraic Number Theory, which might be a good reference for you. But note that this book may not contain some of the new algorithms. | |
| May 28, 2016 at 20:52 | comment | added | WhatsUp | There certainly exist such algorithms. Just construct the field generated by all these $\alpha_i$, and the problem reduces to checking whether a determinant is non-zero. Unfortunately I cannot give a reference, but there are many good books about computational number theory that you can have a look. | |
| May 28, 2016 at 20:30 | history | asked | Pranjal Dutta | CC BY-SA 3.0 |