Timeline for Basis for the Algebraic numbers over the rationals
Current License: CC BY-SA 2.5
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 30, 2022 at 3:30 | comment | added | wilsonw | I think the LLL algorithm works only over real bases, and it is notoriously difficult to check whether a real number is rational. | |
| Dec 2, 2010 at 12:47 | vote | accept | mathahada | ||
| Dec 3, 2010 at 14:25 | |||||
| Dec 2, 2010 at 4:18 | comment | added | Joel David Hamkins | Russell has now explained a similar argument. | |
| Dec 1, 2010 at 14:57 | comment | added | Joel David Hamkins | I think you propose that if we have a finite linearly independent set $B_0$ of algebraic numbers and $\mathbb{Q}(B_0)=\text{Span}(B_0)$, then we consider the next algebraic number $x$. Using the LLL algorithm, we determine if $x$ is in $\mathbb{Q}(B_0)$; if it is, then discard; if not, then add $x$ to the basis by expanding $B_0$ to a linearly independent set $B_1$ with $x\in B_1$ such that $\mathbb{Q}(B_1)=\text{Span}(B_1)$. That sounds very promising, but I don't quite see all the details for the final step of constructing $B_1$. May I kindly ask that you explain it more fully in an answer? | |
| Dec 1, 2010 at 14:56 | comment | added | Joel David Hamkins | I understand your proposal better now. What concerned me is that there are computable vector spaces that have no computable basis, and in such a space, the dependency problem is undecidable---one cannot in general computably determine if one vector is in the span of a finite list of other vectors, even when the ambient space is computably presented. You propose to get around that....(continued) | |
| Dec 1, 2010 at 4:41 | comment | added | Jared Weinstein | No no, I really meant the basis part of the question! Given a finite set B of algebraic numbers (described, let's say, using their minimal polynomials, together with sufficiently many decimal digits), and another algebraic number x, I thought it could be decided in finite time whether x belongs to the span of B. Certainly it can be decided whether x belongs to the field generated by B (by factoring the minpoly of x over that field), and the rest is linear algebra. What am I missing? | |
| Dec 1, 2010 at 3:54 | comment | added | Joel David Hamkins | Jared, if I understand you, what you are talking about why $\mathbb{A}$ has a computable presentation, and that part is fine; it does have a computable presentation, in part for the reasons you mention. But next, having the computable presentation of $\mathbb{A}$, you want to build the basis, and here you include a new element in the basis exactly when it is not in the span of what came earlier. This seems to be a $\Pi^0_1$ question (a $\forall$ question in arithmetic), since you are considering all rational linear combinations of the earlier numbers on the list. | |
| Dec 1, 2010 at 3:43 | comment | added | Jared Weinstein | "At each stage of his construction, he is asking a negated existential question 'is this number not in the span of the earlier numbers?', which we cannot expect to answer computably in finite time." Joel, can you comment on why this is so? Let's suppose that after every iteration of Kevin's construction, you throw in enough new elements so that what you have is the basis for a field, call it K. Then you look up the next polynomial on your list; you have to decide whether each of its roots belong to K or not. But this can be accomplished using the LLL algorithm. | |
| Dec 1, 2010 at 3:12 | history | edited | Joel David Hamkins | CC BY-SA 2.5 |
deleted 26 characters in body
|
| Dec 1, 2010 at 2:47 | history | edited | Joel David Hamkins | CC BY-SA 2.5 |
added 384 characters in body
|
| Dec 1, 2010 at 2:38 | history | answered | Joel David Hamkins | CC BY-SA 2.5 |